Binary Tree Level Order Traversal

Leave a comment

December 12, 2016 by oneOokay

Iterative的话就是用Queue了。以下两种方法来indicate什么时候把tmpList加入到ans里面:

  • curLevel 和 nextLevel: 当curLevel == 0时。这个已经非常熟悉了,现在第一个是想到的这个。
  • size = queue.size()也可以,代码就是这个。

Recursive:这个用Recursive来DFS。

应该想清楚recursive的实质,再想怎么构造吧。这个是从Root开始往左走下去,如果深度大于等于list.size(),那么就需要先在list里面加入一个new list来hold住当前这个node的值。所以先新加入一层,然后add node.val。如果深度符合条件那么只需要取到当前hold住这个node的list(根据height来判断ans.get(height)),往其中add node.val就可以了。

List: list.get(index)

类似的:Binary Tree Zigzag Level Order Traversal

Recursive:

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans  = new ArrayList<>();
        if (root == null){
            return ans;
        }
        
        helper(root, ans, 0);//起始height为0。之后list.get(height)
        return ans;
    }
    
    private void helper(TreeNode node, List<List<Integer>> list, int height){
        if (node == null){
            return;
        }
        if (height >= list.size()){
            list.add(new ArrayList<Integer>());
        }
        list.get(height).add(node.val); //这里也可以把
它放到两个helper之后。具体的见LevelOrder Traversal II
        helper(node.left, list, height + 1);
        helper(node.right, list, height + 1);
    }

Iterative:

private List ans;
    public List levelOrder(TreeNode root) {
        ans = new ArrayList<>();
        if (root == null){
            return ans;
        }
        Queue queue = new LinkedList();
        queue.offer(root);
        List tmp = new ArrayList();
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size > 0){
                TreeNode node = queue.poll();
                size --;
                tmp.add(node.val);
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
            ans.add(tmp);
            tmp = new ArrayList();
        }
        return ans;
    }
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: