leetcode Question 12: Binary Tree Level Order Traversal

Binary Tree Level Order Traversal


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


Update 201402
Analysis:

The standard way of doing this level traversal is using one queue holding pairs (<treenode, level>). The code is listed below, since the output of this problem is the vectors of each level, just be careful that the last level output (Line 38 in the code).

Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > res; //result vector
        queue<pair<TreeNode*,int> > q; //travseral queue
        vector<int> res_tmp; // level vector
        
        if (!root){return res;}
        q.push(make_pair(root,1)); //push the root into the queue
        int level=1; //previous level
        while (!q.empty()){
            pair<TreeNode*,int> tmp = q.front();
            q.pop();
            if (tmp.second!=level){ //if current element has a new level
                level = tmp.second;
                res.push_back(res_tmp); //push the level vector to result
                res_tmp.clear();  //clear the level vector to store the new level
            }
            
            res_tmp.push_back(tmp.first->val); //push the current value to the level vector
            
            if (tmp.first->left!=NULL){
                q.push(make_pair(tmp.first->left,tmp.second+1));
            }
            if (tmp.first->right!=NULL){
                q.push(make_pair(tmp.first->right,tmp.second+1));
            }
        }
        res.push_back(res_tmp); // the last level also needs to push into the result
        return res;
    }
};





Another solution:


Analysis:
The output is slightly different from the classical level-order problem, which do not require the level information. So in this problem one way to get the level is using another queue to save the current level nodes.

The main steps are:
1. Push the root node into queue 1, which is level 1 (or 0)
2. Pop all the nodes from queue 1 to get the current level, for each poped node, push their left child and right child into queue 2.
3. Set queue 1 = queue 2.
4. clear queue 2.




The source code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        queue<TreeNode*> q1,q2;
        vector<vector<int> > res;
        if (root!=NULL){
            q1.push(root);
            vector<int> lres;
            TreeNode *cnode;
            while (true) {
                while (!q1.empty()){ //save one level
                    cnode =q1.front();
                    q1.pop();
                    if (cnode->left!=NULL){q2.push(cnode->left);}
                    if (cnode->right!=NULL){q2.push(cnode->right);}            
                    lres.push_back(cnode->val);
                }
                res.push_back(lres);
                lres.clear();
                q1 = q2;
                while (!q2.empty()) {q2.pop();}
                if (q1.empty()){return res;}
            }
        }
        return res;
        
    }
};

Code(Python):

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

class Solution:
    # @param root, a tree node
    # @return a list of lists of integers
    def levelOrder(self, root):
        q1 = []
        q2 = []
        res = []
        if root == None:
            return res
        q1.append(root)
        l = []
        while True:
            while len(q1) !=0 :
                node = q1.pop(0)
                if node.left != None:
                    q2.append(node.left)
                if node.right != None:
                    q2.append(node.right)
                l.append(node.val)    
            res.append(l)
            l = []
            q1 = q2
            q2 = []
            if len(q1) == 0:
                return res;
         

7 comments:

  1. We can use pair to store level of node and push in vector at that level number.
    vector> ans;
    if(root == NULL)return ans;
    queue> q;
    pair p;
    q.push(make_pair(root,0));
    while(!q.empty()){
    p = q.front();
    TreeNode *head = p.first;
    int level = p.second;
    vector v;
    if(level == ans.size())ans.push_back(v);
    ans[level].push_back(head->val);
    q.pop();
    if(head->left!=NULL)q.push(make_pair(head->left,level+1));
    if(head->right!=NULL)q.push(make_pair(head->right,level+1));
    }
    return ans;

    ReplyDelete
  2. One queue is sufficient if a counter is maintained to hold the number of nodes at each level. This will avoid copying and clearing the second queue.
    BTW nice work on all the solutions, it was really helpful to me

    ReplyDelete
    Replies
    1. Thanks for your reply.
      I have added the 1 queue solution in this post.

      Delete
  3. Another method to avoid using pair type and two queues is to use a sentinel (such as a NULL pointer) to indicate the traversal of a level is complete. For example, if we pop a node from queue and find it is a sentinel, then we know that all nodes in this level have been visited and flush these nodes into result. In addition, we know that all nodes in next level have been pushed in the queue, so we can push the sentinel back to the queue to indicate the end of next level. Here is the code passed Leetcode:

    vector > levelOrder(TreeNode *root) {
    vector > res;
    if(!root) return res;

    std::queue que;
    que.push(root);
    que.push(NULL);
    vector level;

    while(!que.empty()) {
    TreeNode* cur = que.front();
    que.pop();
    if(!cur) {
    if(que.size()!=0)
    que.push(NULL);
    res.push_back(level);
    level.clear();
    }
    else {
    level.push_back(cur->val);
    if(cur->left) que.push(cur->left);
    if(cur->right) que.push(cur->right);
    }
    }
    return res;
    }

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
  4. This comment has been removed by the author.

    ReplyDelete
  5. How are a solution like this one?
    I am not sure why the time complexity of the solution is bad. I am using preorder and the complexity is at the worst O(n)

    vector> preOrder(TreeNode* root, int level)
    {
    if(root)
    {
    if(vec.size() < level){
    vector a;
    a.push_back(root->val);
    vec.push_back(a);
    }
    else
    vec[level-1].push_back(root->val);

    preOrder(root->left, level+1);
    preOrder(root->right, level+1);
    }
    return vec;
    }
    vector> levelOrder(TreeNode* root) {
    return preOrder(root, 1);
    }

    ReplyDelete