描述
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
1
2
3
4
5
2
3
4
5
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
1
2
3
4
5
2
3
4
5
解法
因为 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
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
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
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）可选：