重庆做网站制作公司,温州服务专业的网页设计,课程网站建设开题报告,枣庄做网站制作101. 对称二叉树
力扣题目链接
给定一个二叉树#xff0c;检查它是否是镜像对称的。 思路
镜像对称必要的条件就是根节点的左右子树互相对称
左子树的左孩子 右子树的右孩子左子树的右孩子 右子树的左孩子
递归
使用递归前要确定递归的顺序#xff0c;是前序、后序还…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 outsideinside;}bool isSymmetric(TreeNode* root) {if(root nullptr)return true;return cpy(root-left,root-right);}
};迭代
迭代的思路则简单得多我们使用队列将左右子树的结点一对对放进去再一对对拿出来比较即可。
代码如下
class Solution {
public:bool isSymmetric(TreeNode* root) {queueTreeNode* 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;}
};
