List of Depths: Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you’ll have D linked lists).
Hints: #107, #123, #135
解法1
DFS（深度优先）：
1
2
3
4
5
6
7
8
9
10
11
12
|
public void collectDepth(Node node, int depth, List<List> depthLists) {
if (node == null) {
return;
}
if (depthLists.size() < depth) {
depthLists.add(new List());
}
List depthList = depthLists.get(depth - 1);
depthList.add(node);
collectDepth(node.left, depth + 1, depthLists);
collectDepth(node.right, depth + 1, depthLists);
}
|
解法2
BFS（广度优先）：
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
|
public List<List> depthLists(Node root) {
List<List> depthLists = new ArrayList<>();
Queue<Node> queue = new Queue<>();
root.depth = 1;
queue.enqueue(root);
while (!queue.isEmpty()) {
Node node = queue.dequeue();
List depthList = getOrCreateList(depthLists, node.depth);
depthList.add(node);
if (node.left != null) {
node.left.depth = node.depth + 1;
queue.enqueue(node);
}
if (node.right != null) {
node.right.depth = node.depth + 1;
queue.enqueue(node);
}
}
}
List getOrCreateList(List<List> depthLists, int depth) {
if (depthLists.size() < depth) {
depthLists.add(new List());
}
return depthLists.get(depth - 1);
}
|
解法3优化
BFS（广度优先）优化。在解法2中记录了depth，实际上可以不需要。
在广度优先算法中，本身就是按层遍历的，那么第i层的元素可以从第i - 1层中获得，而每一层都是我们要保存下来，所以可以直接获得。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public List<List> depthLists(Node root) {
List<List> depthLists = new ArrayList<>();
List nextLevel = new ArrayList<>();
nextLevel.add(root);
while (!nextLevel.isEmpty()) {
depthLists.add(nextLevel);
List current = nextLevel; // current level
nextLevel = new List(); // prepare for next level
for (Node n : current) {
if (n.left != null) {
nextLevel.add(n.left);
}
if (n.right != null) {
nextLevel.add(n.right);
}
}
}
return depthLists;
}
|
评论