101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 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, 1000] 内
  • -100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

题解：

递归写法：

  1. 确定参数和返回值

    1. 因为比较的是两颗子树是否是相互翻转的，进而判断这两颗子树是不是对称的，所以要比较的是两颗子树，参数为左子树节点和右子树节点
    2. 返回值为boolean类型

  2. 确定递归出口

    比较两个节点值的情况，分为节点为空和节点不为空两种情况。

    首先是节点为空：

    1. 左节点为空，右节点不为空，返回false
    2. 左节点不为空，右节点为空，返回false
    3. 左右节点均为空，两节点对称，返回true

    然后是两节点都不为空：

    1. 左右节点值不相等，返回false
    2. 左右节点值相等，递归比较内外侧左右节点。
      1. 比较内侧，传入左节点的右孩子和右节点的左孩子
      2. 比较外侧，传入左节点的左孩子和右节点的右孩子
      3. 左右都对称返回true，有一侧不对称返回false

递归代码如下：

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
public boolean isSymmetric(TreeNode root) {
    return compare(root.left, root.right);

}

private boolean compare(TreeNode left, TreeNode right) {
    //左右节点都为空时
    if (left == null && right == null) {
        return true;
    }
    //左右节点有一个为空时
    if (left == null && right != null) {
        return false;
    }

    if (left != null && right == null) {
        return false;
    }


    //左右节点均不为空，但是值不相等时
    if (left.val != right.val) {
        return false;
    }

    //比较内侧树,即左节点的右子树和右节点的左子树
    boolean compareOutside = compare(left.right, right.left);
    //比较外侧树，即左节点的左子树和右节点的右子树
    boolean compareInside = compare(left.left, right.right);
    //返回两颗子树的对称结果
    return compareInside && compareOutside;

}

迭代写法：

使用双端队列，将相应对称的节点存入双端队列的两边，然后取出进行比较，看值是否相同，然后依次比较内外子树。

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
35
public boolean isSymmetric(TreeNode root) {
    //双端队列
    Deque<TreeNode> deque = new LinkedList<>();
    //存入左右节点
    deque.offerFirst(root.left);
    deque.offerFirst(root.right);

    while (!deque.isEmpty()){
        TreeNode leftNode = deque.pollFirst();
        TreeNode rightNode = deque.pollLast();
        //左右节点都为空时
        if (leftNode == null && rightNode == null){
            continue;
        }
        //左右节点一颗为空一颗不为空时
        if (leftNode == null || rightNode == null){
            return false;
        }

        //左右节点都不为空但是值不相同时
        if (leftNode.val != rightNode.val){
            return false;
        }

        //存入外侧节点
        deque.offerFirst(leftNode.left);
        deque.offerLast(rightNode.right);
        //存入内侧节点
        deque.offerFirst(leftNode.right);
        deque.offerLast(rightNode.left);

    }
    return true;

}