# 描述

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

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

题目链接:对称二叉树 (opens 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;
  }
}

# 递归

递归的方式写起来比较简单,维持两个指针,从根节点开始分别判断子树的 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);
}

复杂度分析

假设树上一共 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);
};

复杂度分析

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

# 总结

学到了两个操作符:

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

可以结合 VScode 的 Code Runner 插件 配置 TS,进行代码调试,两种方式(Node or Deno)可选:

上次更新: 4/21/2021, 10:23:16 AM