内容简介:请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。树的结构如下:
文章目录
- 面试题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); }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。