BinaryTreeLevelOrderTraversalII

BinaryTreeLevelOrderTraversalII.java

public class BinaryTreeLevelOrderTraversalII {
    public List<List<Integer>> levelOrderBottom(final TreeNode root) {

        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null)
            return result;

        Stack<List<TreeNode>> stack = new Stack<List<TreeNode>>();
        levelOrderTraversal(root, stack);
        fillResult(result, stack);
        return result;
    }

    private void fillResult(List<List<Integer>> result, Stack<List<TreeNode>> stack) {
        while (!stack.isEmpty()) {
            List<Integer> list = convertToIntegerList(stack.pop());
            result.add(list);
        }
    }

    private void levelOrderTraversal(TreeNode root, Stack<List<TreeNode>> stack) {
        Queue<TreeNode> current = new LinkedList<TreeNode>();
        Queue<TreeNode> next = new LinkedList<TreeNode>();
        current.offer(root);
        stack.push(new ArrayList<TreeNode>(current));

        while (!current.isEmpty()) {
            TreeNode node = current.poll();
            if (node.left != null) {
                next.offer(node.left);
            }
            if (node.right != null) {
                next.offer(node.right);
            }
            if (current.isEmpty()) {
                if (!next.isEmpty()) {
                    stack.push(new ArrayList<TreeNode>(next));
                }
                current = next;
                next = new LinkedList<TreeNode>();
            }
        }
    }

    private List<Integer> convertToIntegerList(List<TreeNode> nodes) {
        List<Integer> result = new ArrayList<Integer>();
        for (TreeNode node : nodes) {
            result.add(node.val);
        }
        return result;
    }
}