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

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;

We can use pair to store level of node and push in vector at that level number.

ReplyDeletevector> 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;

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.

ReplyDeleteBTW nice work on all the solutions, it was really helpful to me

Thanks for your reply.

DeleteI have added the 1 queue solution in this post.

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:

ReplyDeletevector > 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;

}

This comment has been removed by the author.

DeleteThis comment has been removed by the author.

ReplyDeleteHow are a solution like this one?

ReplyDeleteI 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);

}