卖萌的弱渣

I am stupid, I am hungry.

Binary Tree Zigzag Level Order Traversal

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).

Example:

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

1
2
3
4
5

3
   / \
  9  20
/  \
   15   7

return its zigzag level order traversal as:

1
2
3
4
5

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

Solution

  • Java: DFS
(Binary-Tree-Zigzag-Level-Order-Traversal.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = LinkedList<List<Integer>>();
        travel(root,ret,0);
    }

    public void travel(TreeNode node, List<List<Integer>> ret, int level){
        if(node==null) return ;

        if(ret.size() <= level){
            List<Integer> newLevel = new LinkedList<Integer>();
            ret.add(newLevel);
        }

        List<Integer> collection = ret.get(level);
        if(level%2 == 0)
            collection.add(node.val);
        else
            collection.add(0,node.val);

        travel(node.left, ret, level+1);
        travel(node.right, ret, level+1);

    }
}
  • Python: BFS
(Binary-Tree-Zigzag-Level-Order-Traversal.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        ret = []
        stack = []
        level = 0
        stack.append(root)
        while stack:
            newstack = []
            if level % 2 == 0:
                ret.append([x.val for x in stack])
            else:
                ret.append([stack[x].val for x in range(len(stack)-1,-1,-1)])

            for node in stack:
                if node.left:
                    newstack.append(node.left)
                if node.right:
                    newstack.append(node.right)
            level += 1
            stack = newstack
        return ret