Cracking Coding Interview - 4.3 List of Depths

2019-08-14 1 分钟阅读 ARTS-A

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;
}
Cracking Coding Interview - 4.2 Minimal Tree
Cracking Coding Interview - 4.4 Check Balanced

版权

CC BY-NC-ND 4.0

相关文章

评论