Tree Level Order Traversal

Level Order Traversal

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>(); 
        if(root == null) return result; 
        
        ArrayList<Integer> item = new ArrayList<Integer>();
        LinkedList<TreeNode> nodeList = new LinkedList<TreeNode>();
        nodeList.add(root); 
        int currentLevel = 1;
        int nextLevel = 0; 
        while(currentLevel > 0) { 
            TreeNode p = nodeList.poll();
            item.add(p.val);
            currentLevel --; 
            if(p.left != null) {
                nodeList.add(p.left);
                nextLevel ++; 
            }
            if(p.right != null) {
                nodeList.add(p.right);
                nextLevel ++;
            }
            
            if(currentLevel == 0) {
                currentLevel = nextLevel; 
                nextLevel = 0; 
                result.add(0, new ArrayList<Integer>(item));
                item.clear();
            }
        }
        
        return result; 
    }
}