LeetCode - Algorithms - 102. Binary Tree Level Order Traversal

Although its performance is not good, solution of Binary Tree Level Order Traversal is clear.

Java

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
    	List<List<Integer>> result = new ArrayList<List<Integer>>();
    	if (root==null) return result;
    	Map<Integer,List<Integer>> map = new TreeMap<Integer,List<Integer>>();
		updateMap(root,0,map);

    	for(Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
    		result.add(entry.getValue());
    	}
    	return result;        
    }

    private void updateMap(TreeNode root, int level, Map<Integer,List<Integer>> map) {
    	if (root == null) return;
    	++level;
    	if (map.containsKey(level)) {
    		map.get(level).add(root.val);
    	}
    	else {
    		List<Integer> list = new ArrayList<Integer>();
    		list.add(root.val);
    		map.put(level, list);
    	}
    	updateMap(root.left,level,map);
    	updateMap(root.right,level,map);
    	return;
    }    
}

Submission Detail

  • 34 / 34 test cases passed.
  • Runtime: 6 ms
  • Your runtime beats 3.09 % of java submissions.