树的结构

题目链接-来源：力扣（LeetCode）

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [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

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

思路：

我们要判断镜像，关键在于找到每个节点应该比较的对象。对于任意两个节点 L 与 R，它们是否镜像取决于对应的子节点是否镜像，即 L.left 与 R.right， 还有 L.right 与 R.left是否镜像。于是我们可以这样递归地往下判定，直到最低层向上递归地返回判定结果。
需要返回 false 的情况有

  • 两节点不全为空
  • 两节点均不空时值不相等
  • 传递镜像位置子节点返回 false 判定。
    时间复杂度：O(n)
    空间复杂度：O(n)

实现：

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
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.left == null && root.right == null) {
            return true;
        }
        if (root.left == null || root.right == null) {
            return false;
        }
        
        
        return isMirror(root.left, root.right); 
    }
    
    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        
        return isMirror(left.left, right.right) && isMirror(left.right, right.left);
        
    }
}