Binary Tree Zigzag Level Order Traversal

Question

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

return its zigzag level order traversal as:

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

Answer 1

For example, the zig zag level order output of the tree above is:

3 
20 9
15 7

This question is a variation of the question Printing a Binary Tree in Level Order.

Hint:
Queue is not helpful here. You might want to consider using Stack instead.

Solution:
This problem can be solved easily using two stacks (one called currentLevel and the other one called nextLevel). You would also need a variable to keep track of the current level's order (whether it is left->right or right->left).

You pop from stack currentLevel and print the node's value. Whenever the current level's order is from left->right, you push the node's left child, then its right child to stack nextLevel. Remember a Stack is a Last In First OUT (LIFO) structure, so the next time when nodes are popped off nextLevel, it will be in the reverse order.

On the other hand, when the current level's order is from right->left, you would push the node's right child first, then its left child. Finally, don't forget to swap those two stacks at the end of each level (ie, when currentLevel is empty).

void printLevelOrderZigZag(BinaryTree *root) {
    stack<BinaryTree*> currentLevel, nextLevel;
    bool leftToRight = true;
    currentLevel.push(root);
    while (!currentLevel.empty()) {
        BinaryTree *currNode = currentLevel.top();
        currentLevel.pop();
        if (currNode) {
            cout << currNode->data << " ";
            if (leftToRight) {
                nextLevel.push(currNode->left);
                nextLevel.push(currNode->right);
            } else {
                nextLevel.push(currNode->right);
                nextLevel.push(currNode->left);
            }
        }
        if (currentLevel.empty()) {
            cout << endl;
            leftToRight = !leftToRight;
            swap(currentLevel, nextLevel);
        }
    }
}

Answer 2

 class Solution {
    public:
        vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
            vector<vector<int> > rst; 
            if(root == NULL) return rst;

            queue<pair<TreeNode *, int> > q; 
            pair<TreeNode *, int> tmp;
            vector<int> level; 
            int cl = 0; 
            bool zz = true; 
            level.push_back(root->val); 
            if(root->left != NULL) q.push(pair<TreeNode *, int>(root->left, 1));
            if(root->right != NULL) q.push(pair<TreeNode *, int>(root->right, 1));

            while(!q.empty()) {
                tmp = q.front();
                q.pop();
                if(tmp.second != cl) {
                    if(!zz) {
                        reverse(level.begin(), level.end());
                        zz = true;
                    } else zz = false;
                    rst.push_back(level);
                    cl = tmp.second;
                    level.resize(0);
                }

                level.push_back(tmp.first->val);
                if(tmp.first->left != NULL) q.push(pair<TreeNode *, int>(tmp.first->left, tmp.second + 1)); 
                if(tmp.first->right != NULL) q.push(pair<TreeNode *, int>(tmp.first->right, tmp.second + 1));
            }
            if(!zz) reverse(level.begin(), level.end());
            rst.push_back(level);
            return rst;
        }
    };

Answer 3

    void printzigzag(vector<vector<int> > &rlt, TreeNode * root, int level, bool z)
{
    if(root)
    {
        if(level >= rlt.size())
        {
            vector<int> row;
            row.push_back(root->val);
            rlt.push_back(row);
        }
        else
        {
            if(z)
                rlt[level].push_back(root->val);
            else
                rlt[level].insert(rlt[level].begin(), root->val);
        }
        printzigzag(rlt, root->left, ++level, !z);
        printzigzag(rlt, root->right, level, !z);
    }
}

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    vector<vector<int> > rlt;
    printzigzag(rlt, root, 0, true);
    return rlt;
}

Answer 4

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
    vector<vector<int>> result;
    if (!root)
        return result;

    stack<TreeNode *> left;
    stack<TreeNode *> right;
    bool l = true;
    left.push(root);
    vector<int> st(1, root->val);
    result.push_back(st);
    while(left.size()>0 || right.size()>0) {
        if(l) {
            vector<int> addIn;
            while(!left.empty()) {
                TreeNode *t = left.top();
                left.pop();
                if(t->right)  {
                    right.push(t->right);
                    addIn.push_back(t->right->val);
                }
                if(t->left) {
                    right.push(t->left);
                    addIn.push_back(t->left->val);
                }
            }
            if (addIn.size() > 0)
                result.push_back(addIn);
            l = !l;
        }
        else {
            vector<int> addIn;
            while(!right.empty()) {
                TreeNode *t = right.top();
                right.pop();
                if(t->left) {
                    left.push(t->left);
                    addIn.push_back(t->left->val);
                }
                if(t->right) {
                    left.push(t->right);
                    addIn.push_back(t->right->val);
                }
            }
            if (addIn.size() > 0)
                result.push_back(addIn);
            l = !l;

        }
    }
    return result;
}

Answer 5

uses 2 stacks for alternate levels

/* * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } / public class Solution {

public void helper(ArrayList<ArrayList<Integer>> list,Stack<TreeNode> s1,Stack<TreeNode> s2){
    if(s1.empty() && s2.empty()){
        return;
    }

    ArrayList<Integer> al = new ArrayList<Integer>();
    TreeNode node;
    if(!s1.empty())
    while(!s1.empty()){
        node = s1.pop();
        al.add(node.val);
        if(node.right != null){
        s2.push(node.right);    
        }
        if(node.left != null){
        s2.push(node.left);    
        }
    }

    else{
        while(!s2.empty()){
        node = s2.pop();
        al.add(node.val);
        if(node.left!=null){
        s1.push(node.left);    
        }
        if(node.right != null){
        s1.push(node.right);    
        }    
        }
    }

    list.add(al);
    helper(list,s1,s2);
    return;

}

public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
    // Start typing your Java solution below
    // DO NOT write main() function
    Stack<TreeNode> s1 = new Stack<TreeNode>();
    Stack<TreeNode> s2 = new Stack<TreeNode>();
    //System.out.println(root);

    ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> al = new ArrayList<Integer>();

    if(root != null){
    al.add(root.val);
    list.add(al);
    if(root.left != null){
    s1.push(root.left);    
    }
    if(root.right != null){
    s1.push(root.right);    
    }

    helper(list,s1,s2);
    }
    return list;
}

}

Answer 6

use bfs and record the current level count remain;
when current level count is zero, push new level in queue to result

use a flag to record pushing direction

vector<vector<int> > result;
if(root == NULL) {
    return result;
}
vector<int> node_array;
deque<TreeNode*> q;
TreeNode* node;
bool l2r = true;
int level_cnt = 1;
q.push_back(root);
result.push_back(vector<int>(1, root->val));
while(!q.empty()) {
    node = q.front();
    q.pop_front();
    --level_cnt;

    if (node->left != NULL) {
        q.push_back(node->left);
    }
    if (node->right != NULL) {
        q.push_back(node->right);
    }

    if (level_cnt == 0) {
        //new level
        l2r = !l2r;
        if (l2r) {
            for (deque<TreeNode*>::const_iterator cit = q.cbegin(); cit != q.cend(); ++cit) {
                node_array.push_back((*cit)->val);
            }
        } else {
            for (deque<TreeNode*>::const_reverse_iterator cit = q.crbegin(); cit != q.crend(); ++cit) {
                node_array.push_back((*cit)->val);
            }
        }
        if (!node_array.empty()){
            result.push_back(node_array);
            node_array.clear();
        }
        level_cnt = q.size();
    }
}
return result;

Answer 7

public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

    if(root==null)
        return result;

    LinkedList<TreeNode> q = new LinkedList<TreeNode>();
    ArrayList<Integer> level = new ArrayList<Integer>();
    TreeNode cur = null;
    boolean toLeft = true;

    q.add(root);
    int pCounter = 1;
    while(!q.isEmpty()){
        if(toLeft)
            cur = q.removeFirst();
        else
            cur = q.removeLast();

        pCounter--;
        level.add(cur.val);

        if(toLeft){
            if(cur.left!=null){
                q.addLast(cur.left);                
            }
            if(cur.right!=null){
                q.addLast(cur.right);
            }                
        }else{
            if(cur.right!=null){
                q.addFirst(cur.right);
            }                
            if(cur.left!=null){
                q.addFirst(cur.left);                
            }

        }

        if(pCounter==0){
            toLeft = toLeft^true;
            pCounter=q.size();
            result.add(level);
            level = new ArrayList<Integer>();
        }

    }
    return result;
}

Answer 8

public class Wrapper{
    TreeNode node;
    int level;
    Wrapper(TreeNode n, int l){node = n; level = l;}
}
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> rl = new ArrayList<ArrayList<Integer>>();
    if(root == null) return rl;
    Queue<Wrapper> queue = new LinkedList<Wrapper>();
    queue.add(new Wrapper(root, 0));
    int pLevel = -1;
    ArrayList<Integer> curList = null;
    while(! queue.isEmpty()){
        Wrapper tmp = queue.poll();
        TreeNode cur = tmp.node;
        if(tmp.level != pLevel){
            if(pLevel != -1) rl.add(curList);
            curList = new ArrayList<Integer>();
            pLevel = tmp.level;
        }
        if(tmp.level % 2 == 0) curList.add(cur.val);
        else curList.add(0, cur.val);
        if(cur.left != null) queue.add(new Wrapper(cur.left, pLevel + 1));
        if(cur.right != null) queue.add(new Wrapper(cur.right, pLevel + 1));   
    }
    rl.add(curList);
    return rl;
}

Binary Tree Zigzag Level Order Traversal

Follow this question

Welcome to LeetCode

Related questions