本文共 2025 字,大约阅读时间需要 6 分钟。
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3]
是对称的。
进阶:
你可以运用递归和迭代两种方法解决这个问题吗?
根据题意,要判断二叉树是否对称,就是要比较根节点的左子树和右子树是不是相互翻转的,理解这一点就知道了趋势我们要比较的是来两个数(这两个数是根节点的左右子数),既然要不停的比较左右子树的子节点,所以使用递归是方便的。
对于一颗二叉树,我们如何判断是不是对称的呢?来看看下面的比较过程:
如图中所示的一颗二叉树,先比较左右子树的根节点:
下一步,比较左子树的左孩子和右子树的右孩子是不是相等:
继续比较左子树的右孩子是不是等于右子树的左孩子:
如果满足上述条件,则说明是一颗对称二叉树。
递归三部曲
第一,确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的,进而判断这个树是不是对称树,所以要比较的是两个树,参数自然也是左子树节点和右子树节点。
返回值自然是bool类型。
代码如下:
boolean dfs(TreeNode left, TreeNode right)
第二,终止条件
要比较两个节点数值相不相同,首先要把两个节点为空的情况弄清楚!否则后面比较数值的时候就会操作空指针了。
节点为空的情况有:(注意我们比较的其实不是左孩子和右孩子,所以如下我称之为左节点右节点)
左节点为空,右节点不为空,不对称,return false
左不为空,右为空,不对称 return false
左右都为空,对称,返回true
此时已经排除掉了节点为空的情况,那么剩下的就是左右节点不为空:
左右都不为空,比较节点数值,不相同就return false
此时左右节点不为空,且数值也不相同的情况我们也处理了。
代码如下:
//递归终止条件一:两个节点都为nullif(left==null && right==null){ return true;}//递归终止条件二:两个条件中有一个为空,说明不对称if(left ==null || right==null){ return false;}//递归终止条件三:值判断不相等时if(left.val != right.val){ return false;}
第三,确定单层递归的逻辑
上面实现了一系列条件,下面需要层层调用递归传入每次比较的节点,递归函数中调用函数本身,每次比较如上面图示:
代码如下:
//递归调用:函数方法本身调用本身 //主要判断:1.左节点的左孩子和右节点的右孩子 //2.左节点的右孩子和右节点的左孩子 return dfs(left.left,right.right) && dfs(left.right, right.left);
class Solution { public boolean isSymmetric(TreeNode root) { //根节点为空直接放回true if(root==null){ return true; } //调用递归函数,比较根节点下的左右子树,左右节点 return dfs(root.left, root.right); } //定义一个递归函数,比较左节点,右节点 boolean dfs(TreeNode left, TreeNode right){ //递归终止条件一:两个节点都为null if(left==null && right==null){ return true; } //递归终止条件二:两个条件中有一个为空,说明不对称 if(left ==null || right==null){ return false; } //递归终止条件三:值判断不相等时 if(left.val != right.val){ return false; } //递归调用:函数方法本身调用本身 //主要判断:1.左节点的左孩子和右节点的右孩子 2.左节点的右孩子和右节点的左孩子 return dfs(left.left,right.right) && dfs(left.right, right.left); }}
转载地址:http://clgki.baihongyu.com/