力扣记录：二叉树2二叉树的属性

本次题目

• 101 对称二叉树
• 100 相同的树
• 572 另一个树的子树

101 对称二叉树及相关题目

• 后序遍历：判断根节点的两颗子树是否对称，左子树的最左（外）侧的孩子是否等于右子树最右（外）侧的孩子；左子树的最右（里）侧的孩子是否等于右子树最左（里）侧的孩子。左子树左右中遍历，右子树右左中遍历。
• 注意：左右同时为空或同时不为空且节点数值相等时才对称，否则不对称。
• 递归：返回true或false；判断完成后返回；分别判断外侧和内测的孩子是否对称。
• 迭代：不是深度遍历广度遍历，使用队列或栈（Deque或Queue）判断左右子树是否对称（每次判断队列中相邻两个元素是否相同）。
• 递归：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        //当二叉树为空时直接返回
        if(root == null) return false;
        //开始递归
        return compareLeftRight(root.left, root.right);
    }
    //递归函数，判断两个子树是否对称
    private boolean compareLeftRight(TreeNode left, TreeNode right){
        //左右同时为空或同时不为空且节点数值相等时才对称，否则不对称
        if(left == null && right != null){
            return false;
        }else if(left != null && right == null){
            return false;
        }else if(left == null && right == null){
            return true;
        }else if(left.val != right.val){ //排除掉有可能为空的情况
            return false;
        }
        //继续比较该节点的子树（里侧和外侧）
        boolean inside = compareLeftRight(left.left, right.right);
        boolean outside = compareLeftRight(left.right, right.left);
        //返回结果
        return inside && outside;
    }
}

• 迭代：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        //当二叉树为空时直接返回
        if(root == null) return false;
        //定义队列处理数据
        Queue queue = new LinkedList();
        //初始化，将根节点左右孩子放入队列
        queue.offer(root.left);
        queue.offer(root.right);
        //开始迭代，队列为空时结束
        while(!queue.isEmpty()){
            //将要比较的两个元素出队
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            //两个元素都为空，直接对比接下来两个元素
            if(left == null && right == null) continue;
            //若两个元素不同时为空，或都不为空但元素值不同，则返回false
            if(left == null && right != null) return false;
            if(left != null && right == null) return false;
            if(left.val != right.val) return false;
            //两个元素相同，继续进行下一轮对比（里侧，外侧）
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        //最后返回true
        return true;
    }
}

100 相同的树

• 迭代法：同上，对比的两个元素分别为两个二叉树上相同位置的元素。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //定义队列处理元素
        Queue queue = new LinkedList();
        //初始化，将两个二叉树的根节点入队
        queue.offer(p);
        queue.offer(q);
        //开始迭代，当队列为空时结束
        while(!queue.isEmpty()){
            //将要对比的两个元素出队
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            //两个元素同时为空时直接进行下一轮
            if(left == null && right == null) continue;
            //当两个元素不同时为空，或都不为空但值不相同，直接返回false
            if(left == null && right != null) return false;
            if(left != null && right == null) return false;
            if(left.val != right.val) return false;
            //当两个元素不同时为空且值相等时继续下一轮
            queue.offer(left.left);
            queue.offer(right.left);
            queue.offer(left.right);
            queue.offer(right.right);
        }
        //最后返回true
        return true;
    }
}

572 另一个树的子树

• 递归法：s是r的子树，说明s=r，或s在r的左子树上，或s在r的右子树上。递归查找r、r的左右子树是否等于s，返回布尔值，当找到相等时返回true，否则最后返回false。

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //root为空，直接返回
        if(root == null && subRoot != null) return false;
        //开始递归
        //s=r，或s在r的左子树上，或s在r的右子树上
        boolean s1 = Compare(root, subRoot);
        boolean s2 = isSubtree(root.left, subRoot);
        boolean s3 = isSubtree(root.right, subRoot);
        return s1 || s2 || s3;
    }
    //定义递归函数返回布尔值，当找到相等时返回true，否则最后返回false
    private boolean Compare(TreeNode root, TreeNode subRoot){
        //当同时为空时直接返回true
        if(root == null && subRoot == null) return true;
        //当不同时为空时返回false
        if(root != null && subRoot == null) return false;
        if(root == null && subRoot != null) return false;
        if(root.val == subRoot.val){
            boolean r1 = Compare(root.left, subRoot.left);
            boolean r2 = Compare(root.right, subRoot.right);
            return r1 && r2;
        }
        return false;
    }
}