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;