forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinary Tree Zigzag Level Order Traversal.java
More file actions
executable file
·140 lines (117 loc) · 3.91 KB
/
Copy pathBinary Tree Zigzag Level Order Traversal.java
File metadata and controls
executable file
·140 lines (117 loc) · 3.91 KB
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
M
1531703331
tags: Stack, Tree, BFS
time: O(n)
space: O(n)
#### Queue
- 简单的level traversal.根据level奇数偶数而add到不同位子.
- Option1: based on level % 2, insert to front/end of list
- Option2: based on level, insert right/left of node into queue
```
/*
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).
Example
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
Tags Expand
Tree Search Breadth First Search Queue Binary Tree
*/
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
//BFS. first level = 0; level % 2 = 1, list.add(0, ...)
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> rst = new ArrayList<>();
if (root == null) return rst;
int level = 0, size = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
size = queue.size();
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0 ; i < size; i++) {
TreeNode node = queue.poll();
list.add(node.val);
if (level % 2 == 1) addChild(queue, node.left, node.right);
else addChild(queue, node.right, node.left);
}
level++;
rst.add(list);
}
return rst;
}
private void addChild(Queue<TreeNode> queue, TreeNode nodeA, TreeNode nodeB) {
if (nodeA != null) queue.offer(nodeA);
if (nodeB != null) queue.offer(nodeB);
}
}
/*
Thought:
1. realize: queue is no longer can be used. draw a example map to see why.
Instead, use 2 stacks.
Because we can only take the top of stack, and we are constantly adding to the top of the stac, so we need 2 stacks. One is the current one, will be empty every time when we finish the level. The other one is nextLevel, which holds next level’s nodes temporarily.
2. Use a boolean to track if which level it’s running at.
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: A list of lists of integer include
* the zigzag level order traversal of its nodes' values
*/
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return result;
}
Stack<TreeNode> currentLevel = new Stack<TreeNode>();
Stack<TreeNode> nextLevel = new Stack<TreeNode>();
currentLevel.push(root);
boolean regularOrder = false;
while (!currentLevel.empty()) {
ArrayList<Integer> list = new ArrayList<Integer>();
while (!currentLevel.empty()) {
TreeNode temp = currentLevel.pop();
list.add(temp.val);
if (regularOrder) {
addLevel(nextLevel, temp.right);
addLevel(nextLevel, temp.left);
} else {
addLevel(nextLevel, temp.left);
addLevel(nextLevel, temp.right);
}
}
result.add(list);
regularOrder = !regularOrder;
Stack<TreeNode> tmp = currentLevel;
currentLevel = nextLevel;
nextLevel = tmp;
}
return result;
}
public void addLevel(Stack<TreeNode> level, TreeNode node) {
if (node != null) {
level.push(node);
}
}
}
```