剑指offer 28：对称的二叉树

小半 • 2023年2月3日上午10:54 • 技术随笔 • 阅读 197

对称的二叉树

题目：
给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）

方法一：递归

思路：
首先根节点以及其左右子树要相同；
左子树的左子树和右子树的右子树相同；
左子树的右子树和右子树的左子树也要相同
也可看作是两棵树：
它们的两个根结点具有相同的值
每个树的右子树都与另一个树的左子树镜像对称

类似于后序遍历

递归三步曲：

确定递归函数的参数和返回值
因为我们要比较的是两个节点是否是相等，参数是两个节点
有返回值！类型是Boolean
确定终止条件
左右都为空，对称，返回true
左右任意一边为空，不对称，return false
此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
左右都不为空，比较节点数值，不相同就return false
确定单层递归的逻辑
单层递归的逻辑就是处理左右节点都不为空，且数值相同的情况。
比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
如果左右都对称就返回true ，有一侧不对称就返回false 。

注意：
从root开始往下遍历，不能 if(root1.val==root2.val) 就return true ！此时还未知子树的结果！只能 if(root1.val！=root2.val) 就return false ！

public class Solution {
    boolean isSymmetrical(TreeNode root) {
        return check(root,root);
    }
    
    private Boolean check(TreeNode root1,TreeNode root2){
        // 终止条件
        if(root1==null && root2==null){
            return true;
        }
        if(root1 ==null || root2==null){
            return false;
        }
        if(root1.val!=root2.val){
            return false;
        }
        // 用left和right接住子树遍历的结果
        Boolean left=check(root1.left,root2.right);
        Boolean right=check(root1.right,root2.left);
        
        // 后序遍历   回溯
        return left && right;
    }
}

或者：

 
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }

    boolean check(TreeNode root1,TreeNode root2){
        if(root1==null && root2==null){
            return true;
        }
        if(root1==null || root2==null){
            return false;
        }
        // 后序
        boolean p=check(root1.left,root2.right);
        boolean q=check(root1.right,root2.left);
        return (root1.val==root2.val && p && q);
    }
}