# 对称二叉树（101）
# 题目
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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
# 进阶
你可以运用递归和迭代两种方法解决这个问题吗？
# 算法
# 递归
如果任意一个一个节点left的左子树和这个节点镜像对称的节点right的右子树镜像对称，那么这个树就是对称的二叉树
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
export const isSymmetric = (root) => {
const rec = (left, right) => {
if (!left && !right) return true;
if (!left || !right) return false;
return left.val === right.val && rec(left.left, right.right) && rec(left.right, right.left);
};
return rec(root, root);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 迭代
使用队列queue保存待比较的点，队列中默认推入两次根节点，我们每次取出队列前两个元素保存在nodeleft和nodeRight中，进行判断：
- 当两个节点都不存在时我们继续从队列中取出之后的两个节点判断
- 当两个节点值不同或者任意一个节点不存在时，直接返回
false - 当两个节点值相同时，我们在队列
queue中依次压入nodeLeft的左孩子、nodeRight的右孩子、nodeLeft的右孩子、nodeRight的左孩子
当队列为空跳出循环返回true
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
export const isSymmetric = (root) => {
if (!root) return true;
const queue = [root, root];
while (queue.length) {
const nodeLeft = queue.shift();
const nodeRight = queue.shift();
if (!nodeLeft && !nodeRight) continue;
if ((!nodeLeft || !nodeRight) || (nodeLeft.val !== nodeRight.val)) return false;
queue.push(...[nodeLeft.left, nodeRight.right, nodeLeft.right, nodeRight.left]);
}
return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19