转载请注明出处：http://blog.csdn.net/crazy1235/article/details/51508308

Subject

出处：https://leetcode.com/problems/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},
    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

Explain

层序遍历，从底部开始往上按层输出。
该题目与【102. Binary Tree Level Order Traversal】类似。只不过反过来而已。

Solution

其实，最省事的方法，就是将层序正向输出得到的结果反转一下即可。
使用【102. Binary Tree Level Order Traversal】的方法，得到List之后，然后调用Collections.reverse(list); 方法反转一下就OK。

solution 1

【102】题目中的非递归方法，是使用队列，然后往ArrayList中添加每一层的结果。

将ArrayList改为LinkedList，然后每次添加一层的结果，都添加到头部，即调用 addFirst() 方法。

    /**
     * 3ms <br />
     * beats 34.33% of java submissions
     * 
     * @author jacksen
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();

        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        int i = queue.size(); // 记录每层的结点个数
        TreeNode tempNode = null;
        List<Integer> singleLevel = new ArrayList<>();
        while (!queue.isEmpty()) {
            if (i == 0) {// 一层记录结束
                //
                result.addFirst(singleLevel);

                i = queue.size();
                singleLevel = new ArrayList<>();
            }
            tempNode = queue.poll();
            singleLevel.add(tempNode.val);

            --i;

            if (tempNode.left != null) {
                queue.add(tempNode.left);
            }
            if (tempNode.right != null) {
                queue.add(tempNode.right);
            }

        }
        result.addFirst(singleLevel);
        return result;
    }

LeetCode平台 Run Time 是 3ms 。

solution 2

递归方式

方法二依旧可以按照【102】题目中的递归方法修改一下即可。

    /**
     * 递归方式 <br />
     * 重要的是记录层级<br />
     * 2ms<br />
     * eats81.17% of java submissions
     * 
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom2(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();

        levelRecursion(root, result, 0);

        return result;
    }

    /**
     * 递归方法
     */
    private void levelRecursion(TreeNode node,
            LinkedList<List<Integer>> result, int level) {
        if (node == null) {
            return;
        }
        if (result.size() < level + 1) {// 说明还需要添加一行
            result.addFirst(new ArrayList<Integer>());
        }
        result.get(result.size() - 1 - level).add(node.val);

        levelRecursion(node.left, result, level + 1);
        levelRecursion(node.right, result, level + 1);
    }

LeetCode平台 Run Time 是 2ms 。

so easy~~