LeetCode:103. Binary Tree Zigzag Level Order Traversal

本文为LeetCode:103. Binary Tree Zigzag Level Order Traversal的题解。

题意

一颗给定的二叉树,返回节点值的之子形的便利结果。即,从左到右,然后下一级别是从右到左,如此交替。

例如:

给定二叉树:[3,9,20,null,null,15,7]

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

程序将会返回之字形遍历顺序:

1
2
3
4
5
[
[3],
[20,9],
[15,7]
]

题解

对于第一层遍历,从左到右,添加到一个stack中;对于第二层遍历,pop出来的顺序是从右到左,所以要额外考虑先添加right子节点、再添加left子节点到stack中。

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.util.*;

/**
* https://www.robberphex.com/binary-tree-zigzag-level-order-traversal/
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> levelTraversal = new ArrayList<>();
if (root == null) {
return levelTraversal;
}

// 第level级的节点存储在curLevel中
int level = 0;
Stack<TreeNode> curLevel = new Stack<>();
curLevel.push(root);

// 存储下一级节点
Stack<TreeNode> nextLevel = new Stack<>();

while (!curLevel.isEmpty()) {
// 遍历当前层的节点
List<Integer> traversal = new ArrayList<>();
while (!curLevel.isEmpty()) {
TreeNode cur;
// 对于顺向层,pop是从左到右
// 对于逆向层,pop是从右到左
cur = curLevel.pop();
if (cur == null) {
continue;
}
if (level % 2 == 1) {
nextLevel.push(cur.right);
nextLevel.push(cur.left);
} else {
nextLevel.push(cur.left);
nextLevel.push(cur.right);
}
traversal.add(cur.val);
}
if (!traversal.isEmpty()) {
levelTraversal.add(traversal);
}
level++;
curLevel = nextLevel;
nextLevel = new Stack<>();
}

return levelTraversal;
}

public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.right.right = new TreeNode(5);
List<List<Integer>> res = new Solution().zigzagLevelOrder(root);
System.out.println(res);
// 输出 [[1], [3, 2], [4, 5]]
}
}

LeetCode:103. Binary Tree Zigzag Level Order Traversal

https://robberphex.com/binary-tree-zigzag-level-order-traversal/

作者

Robert Lu

发布于

2019-06-30

许可协议

评论