LeetCode Binary Tree Zigzag Level Order Traversal: 2 Methods of BFS and DFS

Overview

LeetCode Binary Tree Zigzag Level Order Traversal could be again solved by both BFS and DFS with additional checking whether it is a zig level or zag level.

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

For 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]
]

Solution: 2 Methods of BFS and DFS

Basically, this problem could be solved by using the same method in “leetcode: Binary Tree Level Order Traversal I and II“, we just need some additional variable say flag to indicate whether we need to reverse the nodes in the current level or not. We still traverse the tree level by level, when we visit the first level, it is regular order from left to right, next level we need to scan from right to left, the strategy is still we first traverse from left to right and we reverse the nodes in this node, we set the flag to indicate for next level, we don’t need to reverse the node. we continue such process until there is no nodes left.

The above is the essential idea and I give two different implementations by both BFS and DFS methods and both code are accepted by the LeetCode OJ to pass this Binary Tree Zigzag Level Order Traversal problem:

The BFS version:

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
    vector<vector<int>> res;
    if (NULL == root) 
        return res;

    queue<TreeNode *> q[2];
    TreeNode *pNode = NULL;
    int qid = 0; 
    int qid2 = 1;

    q[qid].push(root);
    while (!q[qid].empty()) {
        vector<int> lev;
        while (!q[qid].empty()) {
            pNode = q[qid].front();
            q[qid].pop();
            lev.push_back(pNode->val);
            if (pNode->left) q[qid2].push(pNode->left);
            if (pNode->right) q[qid2].push(pNode->right);
        }
        if (qid & 1)
            reverse(lev.begin(), lev.end()); 
        swap(qid, qid2);
        res.push_back(lev);
    }
    return res;
}

The following is the DFS version:

vector<list<int>> res;
        void dfs(TreeNode *root, int depth) {
            if (res.size() == depth)
                res.push_back(list<int>());

            if (depth & 1)
                res[depth].push_front(root->val);
            else
                res[depth].push_back(root->val);

            if (root->left) dfs(root->left, depth + 1);
            if (root->right) dfs(root->right, depth + 1);
        } 

        vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
            vector<vector<int>> results;
            if (NULL == root) 
                return results;     
            dfs(root, 0);

            for (int i = 0, len = res.size(); i < len; ++i)
                results.push_back(vector<int>(res[i].begin(), res[i].end()));
            return results;
        }

Summary

LeetCode Binary Tree Zigzag Level Order Traversal could be again solved by both BFS and DFS with additional checking whether it is a zig level or zag level.

Written on April 14, 2013