Repository navigation
Expand file tree
/
Copy pathBinary Tree Zigzag Level Order Traversal.java
More file actions
executable file
·146 lines (122 loc) · 4.02 KB
/
Copy pathBinary Tree Zigzag Level Order Traversal.java
File metadata and controls
executable file
·146 lines (122 loc) · 4.02 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
141
142
143
144
145
146
M
简单的level traversal.根据level奇数偶数而add到不同位子.
```
/*
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;
* }
* }
*/
//Recap 02.23.2015. BFS. first level = 0; level % 2 = 1, list.add(0, ...)
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>> rst = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return rst;
}
int level = 0;
int size = 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
size = queue.size();
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0 ; i < size; i++) {
TreeNode node = queue.poll();
if (level % 2 == 0) {
list.add(node.val);
} else {
list.add(0, node.val);
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
level++;
rst.add(list);
}
return rst;
}
}
/*
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);
}
}
}
```