# 判断是否为对称二叉树
leetcode：剑指offer：对称二叉树题链
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的
TreeNode
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
1
2
3
4
5
6
7
2
3
4
5
6
7
# 递归解法
- 简洁明了，美丽大方
- true
- 都为null
- 值相等
- false
- 一方为null,另一方不为null
- 值不相等
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function (root) {
if (root === null) {
return true
}
const judge = (r1, r2) => {
if (r1 === r2 && r2 === null) {
return true
}
if (r1 === null || r2 === null) {
return false
}
return r1.val === r2.val && judge(r1.left, r2.right) && judge(r1.right, r2.left)
}
return judge(root.left, root.right)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 中序遍历解法
如果是对称的，则中序遍历结果数组一定是对称的
中序遍历规则：左根右
上图是一种特殊情况:其中序遍历结果[2,2,1,2,2]但不对称，此时需要对比节点所在层数,[3,2,1,3,2]，所以得出下面的代码
var isSymmetric = function (root) {
if (root === null) {
return true
}
const res = [] // 中序遍历结果
const level = [] // 存放每个值所在的层数
const midTravsere = (root, deep) => {
if (!root) {
return
}
midTravsere(root.left, deep + 1)
res.push(root.val)
level.push(deep)
midTravsere(root.right, deep + 1)
}
midTravsere(root, 1)
// 左右镜像节点进行对比，如果值不一样或者值一样层数不一样都为false
for (let i = 0, j = res.length - 1; i < j; i++ , j--) {
if (res[i] !== res[j] || level[i] !== level[j]) {
return false
}
}
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
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 层序遍历
...未完待续