tag:blogger.com,1999:blog-8522573717713847738.post3468452233521743102..comments2024-03-28T00:14:29.070-07:00Comments on Yu's Coding Garden : leetcode Question 12: Binary Tree Level Order TraversalAnonymoushttp://www.blogger.com/profile/00263085222060621782noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-8522573717713847738.post-75887178672389893812016-01-07T21:28:51.797-08:002016-01-07T21:28:51.797-08:00How are a solution like this one?
I am not sure wh...How are a solution like this one?<br />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)<br /><br /> vector> preOrder(TreeNode* root, int level)<br /> {<br /> if(root)<br /> {<br /> if(vec.size() < level){<br /> vector a;<br /> a.push_back(root->val);<br /> vec.push_back(a);<br /> }<br /> else<br /> vec[level-1].push_back(root->val);<br /> <br /> preOrder(root->left, level+1);<br /> preOrder(root->right, level+1);<br /> }<br /> return vec;<br /> }<br /> vector> levelOrder(TreeNode* root) {<br /> return preOrder(root, 1);<br /> }Anonymoushttps://www.blogger.com/profile/04539150202877715894noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-35323540486826299892014-09-19T14:10:44.155-07:002014-09-19T14:10:44.155-07:00This comment has been removed by the author.Yanbing Shihttps://www.blogger.com/profile/16541941455216571610noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-52593353529581232272014-09-19T14:09:08.491-07:002014-09-19T14:09:08.491-07:00This comment has been removed by the author.Yanbing Shihttps://www.blogger.com/profile/16541941455216571610noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-2580294376649567342014-09-19T13:43:17.133-07:002014-09-19T13:43:17.133-07:00Another method to avoid using pair type and two qu...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:<br /> <br /> vector > levelOrder(TreeNode *root) {<br /> vector > res;<br /> if(!root) return res;<br /> <br /> std::queue que;<br /> que.push(root);<br /> que.push(NULL);<br /> vector level;<br /> <br /> while(!que.empty()) {<br /> TreeNode* cur = que.front();<br /> que.pop();<br /> if(!cur) {<br /> if(que.size()!=0) <br /> que.push(NULL);<br /> res.push_back(level);<br /> level.clear();<br /> }<br /> else {<br /> level.push_back(cur->val);<br /> if(cur->left) que.push(cur->left);<br /> if(cur->right) que.push(cur->right);<br /> }<br /> }<br /> return res;<br /> }Yanbing Shihttps://www.blogger.com/profile/16541941455216571610noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-2465011485357243202014-02-05T06:34:49.475-08:002014-02-05T06:34:49.475-08:00Thanks for your reply.
I have added the 1 queue so...Thanks for your reply.<br />I have added the 1 queue solution in this post. <br /><br />Anonymoushttps://www.blogger.com/profile/00263085222060621782noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-31312490473678706012014-02-04T23:59:07.555-08:002014-02-04T23:59:07.555-08:00One queue is sufficient if a counter is maintained...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.<br />BTW nice work on all the solutions, it was really helpful to meVarun Noti Balahttps://www.blogger.com/profile/10636649091415803726noreply@blogger.comtag:blogger.com,1999:blog-8522573717713847738.post-71663773113983602092014-01-22T10:53:01.518-08:002014-01-22T10:53:01.518-08:00We can use pair to store level of node and push in...We can use pair to store level of node and push in vector at that level number.<br />vector> ans;<br /> if(root == NULL)return ans;<br /> queue> q;<br /> pair p;<br /> q.push(make_pair(root,0));<br /> while(!q.empty()){<br /> p = q.front();<br /> TreeNode *head = p.first;<br /> int level = p.second;<br /> vector v;<br /> if(level == ans.size())ans.push_back(v);<br /> ans[level].push_back(head->val);<br /> q.pop();<br /> if(head->left!=NULL)q.push(make_pair(head->left,level+1));<br /> if(head->right!=NULL)q.push(make_pair(head->right,level+1));<br /> }<br /> return ans;Anonymoushttps://www.blogger.com/profile/11926114344734013227noreply@blogger.com