Binary Tree Zigzag Level Order Traversal

Leave a comment

December 12, 2016 by oneOokay

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

类似:Binary Tree Level Order Traversal

Iterative的话:可以用Collection.reverse(list)或者list.add(0, val). 其次可以用height % 2 == 0或者boolean zigzag ( 一层结束的时候zigzag = !zigzag)来决定是否reverse或者list.add(0, val).

Recursive 也是类似,用height % 2 == 0来判定是否用list.add(0, val)。注意此时Recursion的时候,node.left和 node.right的顺序并不要根据height来交换。

List.add(0, value): 将value插到最前

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null){
            return ans;
        }
        helper(root, ans, 0);
        return ans;
    }
    
    private void helper(TreeNode node, List<List<Intege>> list, int height){
        if (node == null){
            return;
        }
        
        if (height >= list.size()){
            list.add(new ArrayList());
        }
        
        if (height % 2 == 0){
            list.get(height).add(node.val);
        }else {
            list.get(height).add(0, node.val);
        }
        helper(node.left, list, height + 1);//node.left和node.right的顺序不
需要根据height变换
        helper(node.right, list, height + 1);
    }

asdf

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: