Simple Solution, using List


  • 0
    public List<List<Integer>> levelOrder(TreeNode root) {
    		List<List<Integer>> tnodes = new ArrayList<List<Integer>>();
    		if(root==null) return tnodes;
    		List<Integer> levels = new ArrayList<Integer>();
    		List<TreeNode> tovisit = new ArrayList<TreeNode>();
    		tovisit.add(root);
    		levels.add(0);
    		while(tovisit.size()>0) {
    			TreeNode visiting = tovisit.remove(0);
    			int level = levels.remove(0);
    			if(tnodes.size()>level) {
    				tnodes.get(level).add(visiting.val);
    			}
    			else {
    				List<Integer> newlevel = new ArrayList<Integer>();
    				newlevel.add(visiting.val);
    				tnodes.add(newlevel);
    			}
    			if(visiting.left!=null) {
    				tovisit.add(visiting.left);
    				levels.add(level+1);
    			}
    			if(visiting.right!=null) {
    				tovisit.add(visiting.right);
    				levels.add(level+1);
    			}
    		}
    		return tnodes;
    	}
    
    1. tovisit<TreeNode> keeps track of the TreeNode we still have to visit
    2. levels<Integer> keeps track of the corresponding level for each node in tovisit<TreeNode>
    3. At every loop we remove the first node in the tovisit List, then we add it to the List in the results at index corresponding to level extracted from the levels<Integer> List.
    4. If the List with that level index is still not present, that means it is the first node for that level. Thus we first create the list for that level, than add the current node to the list, than add this new list to the results.
    5. Finally if the current node has children we add them to the tovisit<TreeNode> List, and the corresponding level to the levels<Integer> List.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.