# 103 二叉树的锯齿形层次遍历
# 题目链接
# 难度：中等
# 思路分析：
广度或者深度，存的顺序要一致和取的顺序按照遍历的方向
# 想
# 一
# 想
# 再
# 看
# 答
# 案
# 想
# 一
# 想
# 再
# 看
# 答
# 案
# 代码：
广度优先： 核心是左侧一直在前面 右侧一直在后面 取的时候按照遍历顺序从前或者从后取
var zigzagLevelOrder = function(root) {
if (root == null) return []
var arr = [root]
var res = []
var go = true
while (arr.length > 0) {
var n = arr.length
var now = []
if (go) {
while (n > 0) {
// 从左侧往右
var node = arr.shift()
now.push(node.val)
// 下一轮是 从右往左
// 从左往右循环一定要用push unshift右侧的值会在前面
if (node.left != null) arr.push(node.left) // 左侧在前面
if (node.right != null) arr.push(node.right) // 右侧在后面
n--
}
res.push(now) // 添加当前层级
} else {
while (n > 0) {
// 从右往左 先取后面的
var node = arr.pop()
now.push(node.val)
// 下一轮是从左往右
// TODO: 从右往左一定要用unshift 用push左边的树的子节点可能会在后面
if (node.right != null) arr.unshift(node.right) // 右侧在后面
if (node.left != null) arr.unshift(node.left) // 左侧在前面
n--
}
res.push(now)
}
go = !go // 更改方向
}
return res
}
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
26
27
28
29
30
31
32
33
34
35
36
37
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 鼓励我一下：
觉得还不错的话，给我的项目点个star吧