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
·106 lines (87 loc) · 2.63 KB
/
Copy pathBinary Tree Level Order Traversal II.java
File metadata and controls
executable file
·106 lines (87 loc) · 2.63 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
M
普通BFS，用一个queue，加上一个queue.size()来交替换行.
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:
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);
}
}
```