【LeetCode】No.101. Symmetric Tree -- Java Version

题目链接：https://leetcode.com/problems/symmetric-tree/

1. 题目介绍（Symmetric Tree）

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

【Translate】： 给定二叉树的根，检查它是否是自身的镜像(即，围绕其中心对称)。

【测试用例】：

示例1：

示例2：

【条件约束】：

【跟踪】：

【Translate】： 你能用递归和迭代求解吗?

2. 题解

2.1 递归

原题解来自于 PratikSen07 的 Easy || 0 ms 100% (Fully Explained)(Java, C++, Python, JS, Python3).

这里的递归思想很简单，即判断了所有的错误情况。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        
        return isSymmetric(root.left, root.right);
        
    }
    
    public boolean isSymmetric(TreeNode left, TreeNode right){
        
        if(left == null && right == null) return true;
        else if(left == null || right == null) return false;
        
        if(left.val != right.val) return false;
        if(!isSymmetric(left.left,right.right) || !isSymmetric(left.right,right.left)) return false;
        
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

2.2 非递归

原题解来自于 iaming 在 Recursive and non-recursive solutions in Java 的 Comment.

其主要的解题思想就是将root的左右子树逐一压入栈，然后弹出，对比该值是否相等，不相等就返回false，然后依次循环遍历所有子树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root.left);
        stack.push(root.right);
        while (!stack.empty()) {
            TreeNode n1 = stack.pop(), n2 = stack.pop();
            if (n1 == null && n2 == null) continue;
            if (n1 == null || n2 == null || n1.val != n2.val) return false;
            stack.push(n1.left);
            stack.push(n2.right);
            stack.push(n1.right);
            stack.push(n2.left);
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33