24
剑指Offer对答如流系列 - 对称的二叉树
source link: https://blog.csdn.net/qq_42322103/article/details/104094911
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
文章目录
- 面试题28：对称的二叉树
面试题28：对称的二叉树
一、问题描述
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
树的结构如下：
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
下图中，A是对称的 B C都不是
二、问题分析
根节点直接比较即可，我们重点分析左右子树。
以上面满足对称的二叉树为例，可以看出，左右子树也刚好是呈镜像的两颗二叉树
在比较的时候我们
对左子树可以采用 父节点–> 左节点 --> 右节点 方式遍历 — 6 5 7
对右子树可以采用 父节点–> 右节点 --> 左节点 方式遍历 — 6 5 7
根据顺序 比较即可。
三、问题解答
public boolean isSymmetrical(TreeNode pRoot){
if(pRoot==null) {
return true; //根结点为null时，认为是对称二叉树
}
return isEqual(pRoot.left,pRoot.right);
}
private boolean isEqual(TreeNode pRoot1,TreeNode pRoot2){
if(pRoot1==null && pRoot2==null) {
return true;
}
if(pRoot1==null || pRoot2==null) {
return false;
}
return pRoot1.val==pRoot2.val
&& isEqual(pRoot1.left, pRoot2.right)
&& isEqual(pRoot1.right, pRoot2.left);
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK