剑指 Offer 28. 对称的二叉树

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

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

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

1
1  / \ 2  2  \  \  3   3

示例 1：

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

示例 2：

1
2
输入：root = [1,2,2,null,3,null,3]
输出：false

限制：

1
0 <= 节点个数 <= 1000

解题思路：（递归）

前序遍历的遍历顺序为根 -> 左 ->右，只要左子树使用根左右遍历，右子树使用根 -> 右 ->左遍历，然后进行比对，如果都相等就为对称二叉树

  • 递归出口：两节点都为空
  • 判断：有一个子节点为空或者两个子节点的值不同，则直接返回false
  • 因为是镜像对称，所以要递归判断第一个节点的左子树和第二个节点的右子树，第一个节点的右子树和第二个节点的左子树

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean isSymmetric(TreeNode root) {
    if(root == null){
        return true;
    }
    
    return recursion(root.left,root.right);
}
boolean recursion(TreeNode root1,TreeNode root2){
    //递归出口，两节点为空
    if(root1 == null && root2 == null){
        return true;
    }
    
    //有一个节点为空或者两者的值不相同，则不对称，直接返回
    if(root1 == null || root2 == null || root1.val != root2.val){
        return false;
    }
    //递归遍历子节点，注意是镜像对称，所以传入的节点应该也是镜像的
    return recursion(root1.left,root2.right) && recursion(root1.right,root2.left);
}