Binary Tree Level Order Traversal II

Leave a comment

December 12, 2016 by oneOokay

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]
]

————

Iterative: 在把list加入ans的时候用ans.add(0, list)
Recursive: 我一度觉得不能用recursive,因为同Iterative,在把list加入到ans的时候是ans.add(0, list)的,这样当ans.get(X)的时候,这个X必须要知道整个tree的高度,用减法算才行。但是recursive要到最后才能够得到整个的height。我错了!!!事实上是在OrderLevelTraversal的时候,用Recursive的时候:
 list.get(height).add(node.val);
 是可以放在以下的之前或者之后都可以的。
若放在前面则是每层都会先加最左的那个元素,第一次到达层底的时候是一个左边的left path
若放在后面则是从最底层开始,填两个儿子之后再填父亲这样。
helper(node.left, list, height + 1);
helper(node.right, list, height + 1);

所以如果用recursive来做这题的话,就一定要把add放在最后了。

感觉那这题和LevelOrderTraversalI相比是一个很好的recursive的例子。

public List<List> levelOrderBottom(TreeNode root) {
        List<List> ans = new ArrayList<>();
        if (root == null){
            return ans;
        }
        
        helper(root, ans, 0);
        return ans;
    }
    
    private void helper(TreeNode node, List<List> ans, int height){
        if (node == null){
            return;
        }
        
        if (height >= ans.size()){
            ans.add(0, new ArrayList());
        }
        
        helper(node.left, ans, height + 1);
        helper(node.right, ans, height + 1);
        ans.get(ans.size() - height - 1).add(node.val);
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: