/
_0103_BinaryTreeZigzagLevelOrderTraversal.java
86 lines (79 loc) · 2.63 KB
/
_0103_BinaryTreeZigzagLevelOrderTraversal.java
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
package com.diguage.algorithm.leetcode;
import com.diguage.algorithm.util.TreeNode;
import java.util.*;
import static com.diguage.algorithm.util.TreeNodeUtils.buildTree;
/**
* = 103. Binary Tree Zigzag Level Order Traversal
*
* https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/[Binary Tree Zigzag Level Order Traversal - LeetCode]
*
* Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
*
* For example:
* Given binary tree `[3,9,20,null,null,15,7]`,
*
* ----
* 3
* / \
* 9 20
* / \
* 15 7
* ----
*
* return its zigzag level order traversal as:
*
* ----
* [
* [3],
* [20,9],
* [15,7]
* ]
* ----
*
* @author D瓜哥, https://www.diguage.com/
* @since 2020-01-24 21:12
*/
public class _0103_BinaryTreeZigzagLevelOrderTraversal {
/**
* Runtime: 1 ms, faster than 75.19% of Java online submissions for Binary Tree Zigzag Level Order Traversal.
*
* Memory Usage: 41.5 MB, less than 5.77% of Java online submissions for Binary Tree Zigzag Level Order Traversal.
*/
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (Objects.isNull(root)) {
return Collections.emptyList();
}
List<List<Integer>> result = new ArrayList<>();
List<TreeNode> level = new ArrayList<>();
level.add(root);
boolean isReverse = false;
while (!level.isEmpty()) {
List<TreeNode> temp = new ArrayList<>();
List<Integer> values = new ArrayList<>(level.size());
for (TreeNode node : level) {
if (isReverse) {
values.add(0, node.val);
} else {
values.add(node.val);
}
if (Objects.nonNull(node.left)) {
temp.add(node.left);
}
if (Objects.nonNull(node.right)) {
temp.add(node.right);
}
}
result.add(values);
level = temp;
isReverse = !isReverse;
}
return result;
}
public static void main(String[] args) {
_0103_BinaryTreeZigzagLevelOrderTraversal solution = new _0103_BinaryTreeZigzagLevelOrderTraversal();
List<List<Integer>> r2 = solution.zigzagLevelOrder(buildTree(Arrays.asList(1, 2, 3, 4, null, null, 5)));
System.out.println(r2);
List<List<Integer>> r1 = solution.zigzagLevelOrder(buildTree(Arrays.asList(3, 9, 20, null, null, 15, 7)));
System.out.println(r1);
}
}