Binary Tree Zigzag Level Order Traversal

Source

• lintcode: 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,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7


return its zigzag level order traversal as:

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

Java

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: A list of lists of integer include 
     *          the zigzag level order traversal of its nodes' values 
     */
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        Stack<TreeNode> cur = new Stack<TreeNode>();
        if(root!=null){
            cur.push(root);
        }
        boolean oddLevel=true;

        while(!cur.isEmpty()){
            Stack<TreeNode> parents = cur;
            cur = new Stack<TreeNode>();
            ArrayList<Integer> res = new ArrayList<Integer>();

            while(!parents.isEmpty()){
                TreeNode p = parents.pop();
                res.add(p.val);

                if(oddLevel){
                    if(p.left!=null){
                        cur.push(p.left);
                    }
                    if(p.right!=null){
                        cur.push(p.right);
                    }
                }
                else{
                    if(p.right!=null){
                        cur.push(p.right);
                    }
                    if(p.left!=null){
                        cur.push(p.left);
                    }
                }
            }
            oddLevel=!oddLevel;
            result.add(res);
        }
        return result;
    }
}

Python

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""


class Solution:
    """
    @param root: The root of binary tree.
    @return: A list of list of integer include 
             the zig zag level order traversal of its nodes' values
    """
    def zigzagLevelOrder(self, root):
        result=[]
        #cur is a stack
        cur=[]
        oddLevel=True

        if root:
            cur.append(root)

        while cur:
            parents = cur
            cur = []
            res=[]
            while parents:
                p = parents.pop()
                res.append(p.val)
                if oddLevel:
                    if p.left:
                        cur.append(p.left)
                    if p.right:
                        cur.append(p.right)
                else:
                    if p.right:
                        cur.append(p.right)
                    if p.left:
                        cur.append(p.left)
            oddLevel = not oddLevel
            result.append(res)
        return result