LeetCode Binary Tree Level Order Traversal I and II: BFS and DFS

Overview

LeetCode Binary Tree Level Order Traversal I and II: Both BFS and DFS could be adopted to solve the problem, open question would be solve II without reversing.

LeetCode Binary Tree Level Order Traversal I and II:

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

The II problem ask you: Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

Analysis: BFS and DFS

The regular level traversal is simple, just use two queues say q1, q2 to store nodes level by level, while printing the nodes in q1, we push all the direct immediate children of the nodes in q1 into q2, that is, we push all the nodes in next level in another queue, after printing and pop all the nodes in q1 out, we repeat the process by exchanging the roles of q1 and q2, that is, we now try to print q2 while push nodes in next level into q1. We continue such a process until there is no nodes left. The following code just implements this idea and is accepted by LeetCode OJ to apss this Binary Tree Level Order Traversal:

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

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

            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);
                }
                swap(qid, qid2);
                results.push_back(lev);
            }
            return results;
        }
};

For II, we first adopt the same algorithm above, and store all the nodes level by level into the final result vector< vector >, we then reverse this result, and get the desired one. Here I use a different angle and use pre-order implementation:

class Solution {
    public:
        vector<vector<int>> ret;
        void dfs(TreeNode *root, int lev) {
            if (ret.size() == lev) {
                ret.push_back(vector<int>());
            }
            ret[lev].push_back(root->val);
            if (root->left) dfs(root->left, lev+1);
            if (root->right) dfs(root->right, lev+1);
        }
        vector<vector<int> > levelOrderBottom(TreeNode *root) {
            if (NULL == root) 
                return ret; 
            dfs(root, 0);
            reverse(ret.begin(), ret.end());
            return ret;
        }
};

**Open questions: **are there any alternative approaches which can tackle the bottom up problem (Binary Tree Level Order Traversal II) without actually reversing the final results?

Summary

LeetCode Binary Tree Level Order Traversal I and II: Both BFS and DFS could be adopted to solve the problem, open question would be solve II without reversing.

Written on April 14, 2013