对称二叉树
本题考二叉树对称,镜像对称,也就是根节点的左子树和右子树是不是相互翻转的,理解这一天我们其实就知道了，这题就是考比较两个树(这两个树是根节点的左右子树)
递归
我们将根节点的左子树记做 left，右子树记做 right。比较 left 是否等于 right，不等的话直接返回就可以了。
如果相当，比较 left 的左节点和 right 的右节点，再比较 left 的右节点和 right 的左节点
比如看下面这两个子树(他们分别是根节点的左子树和右子树)，能观察到这么一个规律：
左子树 22 的左孩子 == 右子树 22 的右孩子
左子树 22 的右孩子 == 右子树 22 的左孩子
2 2 / \ / \ 3 4 4 3 / \ / \ / \ / \ 8 7 6 5 5 6 7 8
下面根据递归三部曲来分析
1.确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否相互翻转，进而判读左右子树是否相等,所以返回值是bool类型,我们要比较的是两个子树,因此参数自然是左子树和右子树。
1. bool dfs(TreeNode* left,TreeNode* right) 2.
2.确定终止条件
- 左右节点都为空
- 两个节点有一个为空
- 两个节点的值不相等
if(left==nullptr&&right==nullptr) { return true; } if(left==nullptr||right==nullptr) { return false; } if(left->val!=right->val) { return false; }
3.确定单层循环的逻辑
递归比较左节点的左孩子和右节点的右孩子；以及比较左节点的右孩子和右节点的左孩子;
return dfs(left->left,right->right) && dfs(left->right,right->left);
代码:
class Solution { public: bool isSymmetric(TreeNode* root) { if(root==nullptr) { return true; } return dfs(root->left,root->right); } bool dfs(TreeNode* left,TreeNode* right) { if(left==nullptr&&right==nullptr) { return true; } if(left==nullptr||right==nullptr) { return false; } if(left->val!=right->val) { return false; } return dfs(left->left,right->right)&&dfs(left->right,right->left); } };
迭代
通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等，如动画所示：
class Solution { public: bool isSymmetric(TreeNode* root) { if(root==nullptr) { return true; } queue<TreeNode*> q; q.push(root->left);// 将左子树头结点加入队列 q.push(root->right);// 将右子树头结点加入队列 while(!q.empty()) { TreeNode* leftNode=q.front();q.pop(); TreeNode* rightNode=q.front();q.pop(); if(leftNode==nullptr&&rightNode==nullptr)// 左节点为空、右节点为空，此时说明是对称的 { continue; } // 接下来就要判断这两个树是否相互翻转 if(leftNode==nullptr||rightNode==nullptr) { return false; } if(leftNode->val!=rightNode->val) { return false; } q.push(leftNode->left); // 加入左节点左孩子 q.push(rightNode->right);// 加入右节点右孩子 q.push(leftNode->right);// 加入左节点右孩子 q.push(rightNode->left); // 加入右节点左孩子 } return true; } };
