Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example: given binary tree {3,9,20,#,#,15,7},
Screen Shot 2016-04-03 at 11.57.32 AM
return its level order traversal as:
Screen Shot 2016-04-03 at 11.57.59 AM
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();   
        levelOrderHelper(root, result, 1);
        return result;
    }
    public void levelOrderHelper (TreeNode root, List<List<Integer>>result, int Depth) {
        if (root == null)
            return; 
        List<Integer> list; 
        if (Depth > result.size()) {
            list = new ArrayList<Integer> (); 
            result.add(list);
        } else {
            list = result.get(Depth-1);
        }
        list.add(root.val);
        levelOrderHelper (root.left, result, Depth+1);
        levelOrderHelper (root.right, result, Depth+1);
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s