day20-101. 对称二叉树

101. 对称二叉树

力扣题目链接

给定一个二叉树，检查它是否是镜像对称的。

101. 对称二叉树

思路

镜像对称必要的条件就是根节点的左右子树互相对称

左子树的左孩子 = 右子树的右孩子
左子树的右孩子 = 右子树的左孩子

递归

使用递归前要确定递归的顺序，是前序、后序还是中序。

这道题用后序遍历比较好。根据上面的比较逻辑，我们可以知道，其实要比较的树就只有根节点的左右两个子树。

我们不妨将之看成两棵树进行比较。

如果是后序遍历，左树的则是先比较外侧再比较内侧，而右树则是先比较外侧再内侧，符合我们的比较顺序。

确定号递归顺序后，我们要确定终止条件

如果左右树均为空，则返回true
如果左右树只有一个为空或者值不相等，返回false
如果左右树存在且值相等，进行单层遍历

单层遍历的逻辑上面已经说过了，先外侧再内侧，因此代码有如下：

class Solution {
public:bool cpy(TreeNode* left, TreeNode* right){if(left == nullptr && right == nullptr)return true;else if(left == nullptr || right == nullptr)return false;else if(left->val != right->val)return false;// 左右子节点存在且值相同bool outside = cpy(left->left,right->right);bool inside = cpy(left->right,right->left);return outside&&inside;}bool isSymmetric(TreeNode* root) {if(root == nullptr)return true;return cpy(root->left,root->right);}
};

迭代

迭代的思路则简单得多，我们使用队列，将左右子树的结点一对对放进去，再一对对拿出来比较即可。

代码如下：

class Solution {
public:bool isSymmetric(TreeNode* root) {queue<TreeNode*> qu;if(root == nullptr)return false;qu.push(root->left);qu.push(root->right);while(!qu.empty()){TreeNode* leftNode = qu.front();qu.pop();TreeNode* rightNode = qu.front();qu.pop();if(leftNode == nullptr && rightNode == nullptr)continue;if(!leftNode || !rightNode || leftNode->val != rightNode->val)return false;qu.push(leftNode->left);qu.push(rightNode->right);qu.push(leftNode->right);qu.push(rightNode->left); }return true;}
};
qu.push(rightNode->left); }return true;}
};