leetcode_【101】对称二叉树

1.题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

>       1
>    /     \
>   2       2
>  /  \    /  \
> 3   4   4   3
>

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

>      1
>     /  \
>    2    2
>     \    \
>      3    3
>

2.解题思路

方法1：递归

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

因此，该问题可以转化为：两个树在什么情况下互为镜像？

如果同时满足下面的条件，两个树互为镜像：

(1)它们的两个根结点具有相同的值。
(2)每个树的右子树都与另一个树的左子树镜像对称。

递归过程：

• 判断两个指针当前节点值是否相等
• 判断 A 的右子树与 B 的左子树是否对称
• 判断 A 的左子树与 B 的右子树是否对称

方法2：迭代

类似于广度优先遍历BFS，用一个队列queue存储左右节点。其中队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像。

(1) 最初，队列中包含的是 root 以及 root。每次提取两个结点并比较它们的值。

(2)当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。

(3)然后，将两个结点的左右子结点按相反的顺序插入队列中。

3.代码

方法1：递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 执行用时 :
     2 ms, 在所有 Java 提交中击败了84.89%的用户
 内存消耗 :
    35.5 MB, 在所有 Java 提交中击败了80.63%的用户

class Solution {
   public static boolean isSymmetric(TreeNode root) {
        if(root == null)
            return true;
        return Symmetric(root.left,root.right);
    }
    public static boolean Symmetric(TreeNode leftroot,TreeNode rightroot) {
        if(leftroot==null && rightroot==null)
            return true;
        if(leftroot==null || rightroot == null)
            return false;
        if(leftroot.val != rightroot.val)
            return false;
        return Symmetric(leftroot.left,rightroot.right) && Symmetric(leftroot.right,rightroot.left);
    }
}

方法2：迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 执行用时 :
    3 ms, 在所有 Java 提交中击败了28.02%的用户
 内存消耗 :

    35.7 MB, 在所有 Java 提交中击败了80.01%的用户

class Solution {
   public static boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
           
            if(node1==null && node2==null)
                continue;
            if(node1==null || node2==null)
                return false;
             if(node1.val!=node2.val)
                return false;
            queue.add(node1.left);
            queue.add(node2.right);
            queue.add(node1.right);
            queue.add(node2.left);
        }
        return true;
    }
}

4.提交记录