题目 给你一个二叉树的根节点 root , 检查它是否轴对称。
示例 1:
输入:root = [1,2,2,3,4,4,3]
输出:true
示例 2:
输入:root = [1,2,2,null,3,null,3]
输出:false
递归思路
-
确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的,进而判断这个树是不是对称树,所以要比较的是两个树,参数自然也是左子树节点和右子树节点。 -
确定终止条件
要比较两个节点数值相不相同,首先要把两个节点为空的情况弄清楚!否则后面比较数值的时候就会操作空指针了。
节点为空的情况有:(注意我们比较的其实不是左孩子和右孩子,所以如下我称之为左节点右节点)
左节点为空,右节点不为空,不对称,return false
左不为空,右为空,不对称 return false
左右都为空,对称,返回true
此时已经排除掉了节点为空的情况,那么剩下的就是左右节点不为空:
左右都不为空,比较节点数值,不相同就return false
此时左右节点不为空,且数值也不相同的情况我们也处理了。 -
确定单层递归的逻辑
此时才进入单层递归的逻辑,单层递归的逻辑就是处理 左右节点都不为空,且数值相同的情况。
比较二叉树外侧是否对称:传入的是左节点的左孩子,右节点的右孩子。
比较内测是否对称,传入左节点的右孩子,右节点的左孩子。
如果左右都对称就返回true ,有一侧不对称就返回false 。
java递归实现
class Solution {
public boolean isSymmetric(TreeNode root) {
//如果根节点为空,则对称
if (root == null)
{
return true;
}
//否则判断左右子树是否对称
return check(root.left, root.right);
}
//判断左右子树是否对称的递归函数
public boolean check(TreeNode node1, TreeNode node2)
{
//都为空是对称
if (node1 == null && node2 == null)
{
return true;
}
//两边节点不相等的情况
if (node1 == null || node2 == null || node1.val != node2.val)
{
return false;
}
return check(node1.left, node2.right) && check(node1.right, node2.left);
}
}