-
Notifications
You must be signed in to change notification settings - Fork 9
/
Binary Tree Zigzag Level Order Traversal (pyemma)
34 lines (31 loc) · 1.4 KB
/
Binary Tree Zigzag Level Order Traversal (pyemma)
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
import java.util.*;
public class BinaryTreeZigzagLevelOrderTraversal {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
ArrayList<TreeNode> stack1 = new ArrayList<TreeNode>();
ArrayList<TreeNode> stack2 = new ArrayList<TreeNode>();
ArrayList<Integer> arr = new ArrayList<Integer>();
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) return res;
stack1.add(root);
while(stack1.size() != 0) {
for(int i = 0; i < stack1.size(); i++) arr.add(stack1.get(i).val);
res.add(new ArrayList<Integer>(arr));
arr.clear();
for(int i = stack1.size()-1; i >= 0; i--) {
if(stack1.get(i).right != null) stack2.add(stack1.get(i).right);
if(stack1.get(i).left != null) stack2.add(stack1.get(i).left);
stack1.remove(i);
}
if(stack2.size() == 0) break;
for(int i = 0; i < stack2.size(); i++) arr.add(stack2.get(i).val);
res.add(new ArrayList<Integer>(arr));
arr.clear();
for(int i = stack2.size()-1; i >= 0; i--) {
if(stack2.get(i).left != null) stack1.add(stack2.get(i).left);
if(stack2.get(i).right != null) stack1.add(stack2.get(i).right);
stack2.remove(i);
}
}
return res;
}
}