BinaryTreeLevelOrderTraversalIIOPT [source code]

public class BinaryTreeLevelOrderTraversalIIOPT {
static

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        helper(res, root, 0);
        return res;
    }

    public void helper(List<List<Integer>> res, TreeNode root, int height) {
        if (root == null) return;
        if (height >= res.size()) {
            //root is the first one visited at this level/height
            res.add(0, new ArrayList<Integer>());
        }
        helper(res, root.left, height + 1);
        helper(res, root.right, height + 1);
        res.get(res.size() - 1 - height).add(root.val);
    }
}

    public static void main(String[] args) {
        BinaryTreeLevelOrderTraversalIIOPT.Solution tester = new BinaryTreeLevelOrderTraversalIIOPT.Solution();
    }
}

这个是 submission 最优解: 2(71);

这个算法本质上还是有点赖皮的, 虽然这个算法本质上是 DFS, 但是这里这个算法本身并不依赖于 DFS 的性质, DFS 只不过是作为一个默认的traversal 的顺序而已;
每一个 node 被标记上了自己的 height, 这样就知道自己在 res 里面的 index1应该是多少; 然后就是不停的查询更新操作而已;
稍微有点想头的就是怎么判断什么时候给 res 加一个 level.
不过这个其实也不是必须这样做, 可以在main 里面先单独走一遍判断max height, 然后初始化给 res 这么多个 level 就行了. 不过这样做就要额外多走一个 pass, 不太聪明;

2018-05-02 20:27:26 这个想法不对啊, 如果unbalanced, 最后这个实际上一个单独的pre beam是无法把所有的level都初始化成功的;

另外注意BFS 和 DFS 判断 Null 的位置的区别. DFS 里面 Null 的判断往往是 recursion 的base case, 然而 BFS 本身是一个 iterative 的写法, 所以直接在循环里面一个 if 就可以判断了;

另外熟悉一下List.add(int, T)这个 API 的用法. 这里就是因为依赖这个 API, 所以不用单独 reverse; 不过 discussion 里面有人提到如果你准备用这个 API, which is position sensitive, 那么最好用 LinkedList, 而不是ArrayList;

You'd better use ArrayList as "list" variable, because "list.get(list.size() - 1 - level).add(node.val)" works O(n)

list.addFirst(), or list.add(0, new ArrayList()) if use ArrayList will be O(n) .

It's trade off between ArrayList.add(0, List) and LinkedList.get(list.size()-1-level). Though both are O(n), the latter cost a bit less than the former, comparing them one to one. However, the former only executes for the leftmost node of each level, while the latter runs for all nodes. Therefore, in case of a complete binary tree, the total cost for former and latter are O(n) and O(n^2), respectively.

意思是如果一定要用这个 DFS 来做, 那么最好干脆最后总的一个 reverse.

其他可行的做法有:

Collections.reverse(counts);  
or  
if (list.size()-1 < level) list.addFirst(new LinkedList<Integer>());

Problem Description

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,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
Difficulty:Easy
Category:Algorithms
Acceptance:39.62%
Contributor: LeetCode
Related Topics
tree breadth-first search
Similar Questions
Binary Tree Level Order Traversal