九旬的博客

描述

给定一个二叉树，检查它是否是镜像对称的。

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

    1
   / \
  2   2
 / \ / \
3  4 4  3
1
2
3
4
5

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

    1
   / \
  2   2
   \   \
   3    3
1
2
3
4
5

题目链接：对称二叉树open in new window

解法

因为 JS 没有二叉树的数据结构，所以新建了一个 TreeNode 的 Class，发现用 TS 写真香...

//Definition for a binary tree node.
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}
1
2
3
4
5
6
7
8
9
10
11

递归

递归的方式写起来比较简单，维持两个指针，从根节点开始分别判断子树的 left === right && right === left 即可。

function isSymmetric(root: TreeNode | null): boolean {
  let check = function(p: TreeNode | null, q: TreeNode | null): boolean {
    // 如果p和q都为null 则说明相同 返回true
    if (!p && !q) return true;
    // 如果p和q有一个是null 则说明不相同 返回false
    if (!p || !q) return false;
    // 如果p和q都有值则开始判断是否相等，如果相等在继续递归判断left和right节点
    return p.val === q.val && check(p.left, q.right) && check(p.right, q.left);
  };
  return check(root, root);
}
1
2
3
4
5
6
7
8
9
10
11

复杂度分析

假设树上一共 n 个节点。

  • 时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。
  • 空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。

迭代

通过维持一个队列，每次将将节点的 left 和 right 分别 push 到队列中，然后迭代进行判断。

const check = (u: TreeNode | null, v: TreeNode | null): boolean => {
  const q: (TreeNode | null)[] = [];
  q.push(u), q.push(v);
  // 逗号操作符  对它的每个操作数求值（从左到右），并返回最后一个操作数的值。
  while (q.length) {
    // ! 表示一定有值
    u = q.shift()!;
    v = q.shift()!;
    // 都为null 则跳出本次循环
    if (!u && !v) continue;
    // 有一个不存在或者不相等，就返回false
    if (!u || !v || u.val !== v.val) return false;
    // push 两棵树，用于下一轮的对比
    q.push(u.left);
    q.push(v.right);
    // push 两棵树，用于下一轮的对比
    q.push(u.right);
    q.push(v.left);
  }
  return true;
};
var isSymmetric = function(root: TreeNode | null): boolean {
  return check(root, root);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

总结

学到了两个操作符:

  • , 逗号操作符 对它的每个操作数求值（从左到右），并返回最后一个操作数的值。
  • ! ! 表示一定有值 或者 表示 当前值不为 null 和 undefined

可以结合 VScode 的 Code Runner 插件 配置 TS，进行代码调试，两种方式（Node or Deno）可选：