【LeetCode】107.Binary Tree Level Order Traversal II解題報告

転載は出典を明記してください。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]
]

エクスプレーン
レイヤーを巡回して、底から上へ層ごとに出力します。このテーマは【102.Binary Tree Level Order Traversal】と似ています。ただの逆です。
Solution
実は、一番手間がかからない方法は、層順順順に出力された結果を反転させることです。「102.Binary Tree Level Order Traversal」という方法を使って、Listを得た後、Collection s.reverseを呼び出します。方法を逆にすればOKです。
ソロ1
【102】タイトルの非再帰方法は、キューを使って、それぞれの層をArayListに追加した結果である。
ArayListをLinked Listに変更し、層を追加するたびにヘッダに追加します。すなわち、addFirst（）メソッドを呼び出します。

    /**
     * 3ms 

     * 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は3 msです。
solution 2
再帰的方式
方法二は相変わらず【102】テーマの再帰的な方法によって修正すればいいです。

    /**
     *      

     *         

     * 2ms

     * eats81.17% of java submissions
     * 
     * @param root
     * @return
     */
    public List> levelOrderBottom2(TreeNode root) {
        LinkedList> result = new LinkedList>();

        levelRecursion(root, result, 0);

        return result;
    }

    /**
     *     
     */
    private void levelRecursion(TreeNode node,
            LinkedList> result, int level) {
        if (node == null) {
            return;
        }
        if (result.size() < level + 1) {//          
            result.addFirst(new ArrayList());
        }
        result.get(result.size() - 1 - level).add(node.val);

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

LeetCodeプラットフォームRun Timeは2 msです。
so easy~