101. 对称二叉树

1、概要

给你一个二叉树的根节点 root ， 检查它是否轴对称。

判断对称二叉树要比较的不是左右节点！是根节点的左子树与右子树是不是相互翻转。

其实要比较的是两个树，即根节点的左右子树。两个子树的里侧和外侧是否相等。

只能是“后序遍历”，要通过递归函数的返回值来判断。准确来说是一个树左右中，一个树右左中。

2、思路

递归法

• 递归函数参数与返回值

参数是左右子树，返回bool

public boolean compare(TreeNode left,TreeNode right)

• 终止条件

要比较两个节点数值相不相同，要把两个节点为空的情况弄清楚，避免空指针

1. 左节点为空，右节点不为空，false
2. 左不为空，右为空，false
3. 左右都为空，true
4. 左右都不空，比较节点数值，不相同false

		//左空 右不空
        if(left == null && right != null){
            return false;
        }
        //左不空 右空
        if(left!= null && right == null){
            return false;
        }
        //左空 右空
        if(left==null && right == null){
            return true;
        }
        //左不空 右不空 但不等
        if(left.val != right.val){
            return false;
        }

• 单层逻辑

单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。

1. 比较外侧：左节点左孩子，右节点右孩子
2. 比较内侧：左节点右孩子，右节点左孩子
3. 都对称返回true，有一侧不对称返回false

		//左不空 右不空 且相等
        //比较外侧，左节点-左孩子 右节点-右孩子
        boolean outside = compare(left.left,right.right);
        //比较内侧，左节点-右孩子 右节点-左孩子
        boolean inside = compare(left.right,right.left);

        return outside && inside;

迭代法

本题的本质是判断两个树是否是相互翻转的，其实已经不是所谓二叉树遍历的前中后序的关系了

可以使用队列来比较两个树（根节点的左右子树）是否相互翻转，（注意这不是层序遍历）

其实是把左右两个子树要比较的元素顺序放进一个容器，然后成对成对的取出来进行比较，那么其实使用栈也是可以的。

3、代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        //return compare(root.left,root.right);
        return compareN(root);
    }
    //迭代 队列 栈一致
    public boolean compareN(TreeNode node){
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(node.left);
        que.offer(node.right);
        while(!que.isEmpty()){
            TreeNode left = que.poll();
            TreeNode right = que.poll();
            if(left == null && right == null){
                continue;
            }
            if(left == null || right == null || left.val != right.val){
                return false;
            }

            que.offer(left.left);
            que.offer(right.right);
            que.offer(left.right);
            que.offer(right.left);
        }
        return true;
    }

    //递归
    public boolean compare(TreeNode left,TreeNode right){
        //左空 右不空
        if(left == null && right != null){
            return false;
        }
        //左不空 右空
        if(left!= null && right == null){
            return false;
        }
        //左空 右空
        if(left==null && right == null){
            return true;
        }
        //左不空 右不空 但不等
        if(left.val != right.val){
            return false;
        }
        //左不空 右不空 且相等
        //比较外侧，左节点-左孩子 右节点-右孩子
        boolean outside = compare(left.left,right.right);
        //比较内侧，左节点-右孩子 右节点-左孩子
        boolean inside = compare(left.right,right.left);

        return outside && inside;
    }
}

相关题目

100. 相同的树

情况均相同，对比同侧即可

compare(left.left,right.left)

compare(left.right,right.right)

572. 另一棵树的子树

终止条件不同

可以是完全相同，可以是左子树，可以是右子树

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return compare(root,subRoot);
    }

    public boolean compare(TreeNode s,TreeNode t){
        
        if(s == null) return false;
        

        return compare(s.left,t) || compare(s.right,t) || same(s,t);
    }

    public boolean same(TreeNode left,TreeNode right){
        if(left == null && right  == null){
            return true;
        }
        if(left == null || right == null || left.val != right.val){
            return false;
        }

        return same(left.left,right.left) && same(left.right,right.right);
    }
}