forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinary Tree Level Order Traversal II.java
More file actions
executable file
·142 lines (123 loc) · 3.85 KB
/
Copy pathBinary Tree Level Order Traversal II.java
File metadata and controls
executable file
·142 lines (123 loc) · 3.85 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
M
普通BFS，用一个queue，加上一个queue.size()来交替换行.
或者多用一个queue来存下个level的nodes
rst里面add(0,...)每次都add在list开头
```
/*
Given a binary tree, return the bottom-up level order traversal of its nodes' values.
(ie, from left to right, level by level from leaf to root).
Example
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
Tags Expand
Queue Binary Tree Binary Tree Traversal Breadth First Search
*/
/**
* 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;
* }
* }
*/
/*
Thoughts:
Breadth first traversal. Add to 0 position every time.
BFS uses a queue for level -> traversal completes when the queue is drained.
Use another queue to store next level, and switch with current queue when need to be.
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
final List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
Queue<TreeNode> queueLevel = new LinkedList<>();
List<Integer> level = new ArrayList<>();
queue.add(root);
while(!queue.isEmpty()) {
final TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queueLevel.add(node.left);
}
if (node.right != null) {
queueLevel.add(node.right);
}
if (queue.isEmpty()) {
queue = queueLevel;
result.add(0, level);
queueLevel = new LinkedList<>();
level = new ArrayList<>();
}
}
return result;
}
}
/*
Thoughts:
1. Non-recursive
similar to Binary Tree Level Order Traversal I, just when adding into the final result,
add to the top all the time. Then the first added will be at the bottom: result.add(0, list)
2. Recursive:
Similar to Level Traversal I, do a dfs. The difference is: everytime, we use ArrayList<ArrayList<>> like a stack by doing add(0, newList);
when populating the levelArrayList, make sure to address the correct corresponding level.
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: buttom-up level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrderButtom(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return result;
}
/*
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<Integer>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode temp = queue.poll();
list.add(temp.val);
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
result.add(0, list);
}*/
dfs(root, 0, result);
return result;
}
public void dfs(TreeNode root, int level, ArrayList<ArrayList<Integer>> rst) {
if (root == null) {
return;
}
if (level >= rst.size()) {
rst.add(0, new ArrayList<Integer>());
}
dfs(root.left, level + 1, rst);
dfs(root.right, level + 1, rst);
rst.get(rst.size() - level - 1).add(root.val);
}
}
```