Binary Tree Level Order Traversal
https://leetcode.com/problems/binary-tree-level-order-traversal
Breadth-first search
BSF has its common pattern.
Pattern for problems with many steps and each step has many ways to next step:
a queue stores [step0, step1, step2, ...]
queue.add(first step)
while queue is not empty
current_step = queue.poll()
// do something here with current_step
// like counting
foreah step in current_step can jump to
queue.add(step)
Apply the pattern
It is easy to search through a binary tree using BSF.
queue.add(root)
while queue is not empty
current_node = queue.poll()
add current_node.value to current level collections
queue.add(current_node.left)
queue.add(current_node.right)
How to know which level current node should be added to
use a dummy node as a separator into the queue, whenever polling a separator from the queue, we know that a level is end.
codes may be like below
queue.add(root)
queue.add(SEP)
while queue is not empty
current_node = queue.poll()
if current_node is SEP
// new level is start
reset current_level collection
queue.add(SEP) // here is added to the end of current level
stop if only SEP in the queue
else
add current_node.value to current_level collection
queue.add(current_node.left)
queue.add(current_node.right)
Source code Read on Github
1 /**
2 * Definition for binary tree
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode(int x) { val = x; }
8 * }
9 */
10 public class Solution {
11 public List<List<Integer>> levelOrder(TreeNode root) {
12
13 ArrayList<List<Integer>> rt = new ArrayList<List<Integer>>();
14
15 if(root == null) return rt;
16
17 final TreeNode END = new TreeNode(0);
18
19 Deque<TreeNode> queue = new LinkedList<TreeNode>();
20
21 queue.add(root);
22 queue.add(END);
23
24 ArrayList<Integer> level = new ArrayList<Integer>();
25
26 while(!queue.isEmpty()){
27
28 TreeNode node = queue.poll();
29
30 if(node == END){
31 rt.add(new ArrayList<Integer>(level)); // copy
32 level.clear();
33
34 if(!queue.isEmpty()) queue.add(END);
35
36 }else{
37
38 level.add(node.val);
39
40 if(node.left != null) queue.addLast(node.left);
41 if(node.right != null) queue.addLast(node.right);
42 }
43 }
44
45 return rt;
46
47 }
48 }