Binary Tree Level Order Traversal II

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

For example:
Given binary tree {3,9,20,#,#,15,7},

结果是straight forward,首先产生一个每个level的node的list, 然后再从bottom开始由每个level的list生成每个level value的list,最后输出就可以得到结果。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        //generate node array for each level
        ArrayList<ArrayList<TreeNode>> tree = new ArrayList<ArrayList<TreeNode>>();
        ArrayList<TreeNode> next = new ArrayList<TreeNode> ();
        if (root != null)
            next.add(root);
        while(!next.isEmpty())
        {
            tree.add(next);
            next = nextLevel(next);
        }
        for (int i = tree.size()-1; i >=0; i--)
        {
            ArrayList<TreeNode> level = tree.get(i);
            ArrayList<Integer> r = new ArrayList<Integer>();
            for (int j = 0; j < level.size(); j++)
            {
                r.add(level.get(j).val);
            }
            result.add(r);
        }
        return result;
        
    }
    
    public ArrayList<TreeNode> nextLevel (ArrayList<TreeNode> nodeList)
    {
        ArrayList<TreeNode> result = new ArrayList<TreeNode>();
        for (TreeNode n : nodeList)
        {
            if (n.left != null)
                result.add(n.left);
            if (n.right != null)
                result.add(n.right);
        }
        return result;
    }
}

Second Submission:

Use an arrayList for each level, much simpler, no need to count the number in a fifo when doing BFS

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null)
            return result;
        ArrayList<TreeNode> level = new ArrayList<TreeNode>();
        level.add(root);
        while(!level.isEmpty()) {
            ArrayList<TreeNode> next = new ArrayList<TreeNode>();
            ArrayList<Integer> num = new ArrayList<Integer>(); // translate to integer
            for (TreeNode t : level) {
                num.add(t.val);
                if (t.left != null)
                    next.add(t.left);
                if (t.right != null)
                    next.add(t.right);
            }
            result.add(0,num);
            level = next;
        }
        return result;
    }
}

2 thoughts on “Binary Tree Level Order Traversal II

  1. Pingback: Binary Tree Level Order Traversal | Hello World

  2. Pingback: Binary Tree Postorder Traversal | Hello World

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