友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

101. 对称二叉树

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

示例 1:

0101 01
输入:root = [1,2,2,3,4,4,3]
输出:true

示例 2:

0101 02
输入:root = [1,2,2,null,3,null,3]
输出:false

提示:

  • 树中节点数目在范围 [1, 1000]

  • -100 <= Node.val <= 100

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

思路分析

为什么执行结果显示递归更快?而不是队列呢?

使用广度优先搜索解决对称问题。

0101 10
0101 11
0101 12
0101 13
0101 14
0101 15
0101 16
0101 17
0101 18
0101 19
0101 20
0101 21
  • 一刷

  • 二刷

  • 三刷

  • 四刷

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
public boolean isSymmetric(TreeNode root) {
    return isMirror(root, root);
}

private boolean isMirror(TreeNode t1, TreeNode t2) {
    if (Objects.isNull(t1) && Objects.isNull(t2)) {
        return true;
    }
    if (Objects.isNull(t1)||Objects.isNull(t2)) {
        return false;
    }
    return (Objects.equals(t1.val, t2.val))
            && isMirror(t1.left, t2.right)
            && isMirror(t1.right, t2.left);
}

/**
 * Runtime: 1 ms, faster than 36.88% of Java online submissions for Symmetric Tree.
 *
 * Memory Usage: 38.9 MB, less than 43.54% of Java online submissions for Symmetric Tree.
 */
public boolean isSymmetricIterative(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode t1 = queue.poll();
        TreeNode t2 = queue.poll();
        if (Objects.isNull(t1) && Objects.isNull(t2)) {
            continue;
        }
        if (Objects.isNull(t1) || Objects.isNull(t2)) {
            return false;
        }
        if (!Objects.equals(t1.val, t2.val)) {
            return false;
        }
        queue.add(t1.left);
        queue.add(t2.right);
        queue.add(t1.right);
        queue.add(t2.left);
    }
    return true;
}

/**
 * Runtime: 228 ms, faster than 36.88% of Java online submissions for Symmetric Tree.
 *
 * Memory Usage: 92.6 MB, less than 5.44% of Java online submissions for Symmetric Tree.
 */
public boolean isSymmetricBfs(TreeNode root) {
    if (Objects.isNull(root)) {
        return true;
    }
    ArrayList<TreeNode> parent = new ArrayList<>();
    parent.add(root);
    while (!parent.isEmpty()) {
        HashSet<TreeNode> nodes = new HashSet<>(parent);
        if (nodes.size() == 1 && nodes.contains(null)) {
            return true;
        }
        ArrayList<TreeNode> children = new ArrayList<>(parent.size() * 2);
        for (TreeNode node : parent) {
            if (Objects.isNull(node)) {
                children.add(null);
                children.add(null);
            } else {
                children.add(node.left);
                children.add(node.right);
            }
        }
        for (int i = 0; i < children.size() / 2; i++) {
            TreeNode left = children.get(i);
            TreeNode right = children.get(children.size() - 1 - i);
            if (Objects.isNull(left) && Objects.isNull(right)) {
                continue;
            }
            if (Objects.isNull(left) || Objects.isNull(right)) {
                return false;
            }
            if (!Objects.equals(left.val, right.val)) {
                return false;
            }
        }
        parent = children;
    }

    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
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-24 16:14
 */
public boolean isSymmetric(TreeNode root) {
  return root == null || isSymmetric(root.left, root.right);
}

private boolean isSymmetric(TreeNode left, TreeNode right) {
  if (left == null && right == null) {
    return true;
  }
  // 前面已经判断都为null的情况了,
  // 这里为了简单,只需要判断一个不为空即可
  if (left == null
    || right == null
    || left.val != right.val) {
    return false;
  }
  // 使用 && 会自动中断后续的递归判断
  return isSymmetric(left.left, right.right)
    && isSymmetric(left.right, right.left);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-09-16 17:51:17
 */
public boolean isSymmetric(TreeNode root) {
  if (root == null) {
    return true;
  }
  return isSymmetric(root.left, root.right);
}

private boolean isSymmetric(TreeNode left, TreeNode right) {
  if (left == null && right == null) {
    return true;
  }
  if (left == null
    || right == null
    || left.val != right.val) {
    return false;
  }
  return isSymmetric(left.left, right.right)
    && isSymmetric(left.right, right.left);
}
 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
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-24 20:40
 */
public boolean isSymmetric(TreeNode root) {
  if (!isSymmetric(root.left, root.right)) {
    return false;
  }
  if (root.left == null) {
    return true;
  }
  List<TreeNode> level = new LinkedList<>();
  level.addFirst(root.left);
  level.addLast(root.right);
  List<TreeNode> nextLevel = new LinkedList<>();
  while (!level.isEmpty()) {
    TreeNode left = level.removeFirst();
    TreeNode right = level.removeLast();
    if (isSymmetric(left.left, right.right)) {
      if (left.left != null) {
        nextLevel.addFirst(left.left);
        nextLevel.addLast(right.right);
      }
    } else {
      return false;
    }
    if (isSymmetric(left.right, right.left)) {
      if (left.right != null) {
        nextLevel.addFirst(left.right);
        nextLevel.addLast(right.left);
      }
    } else {
      return false;
    }
    if (level.isEmpty()) {
      level = nextLevel;
      nextLevel = new LinkedList<>();
    }
  }
  return true;
}

private boolean isSymmetric(TreeNode left, TreeNode right) {
  return left == null && right == null
    || null != left && null != right && left.val == right.val;
}