首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode: 107_Binary Tree Level Order Traversal II | 二叉树自底向上的层次遍历 | Easy

LeetCode: 107_Binary Tree Level Order Traversal II | 二叉树自底向上的层次遍历 | Easy

作者头像
Linux云计算网络
发布2018-01-11 10:51:36
4580
发布2018-01-11 10:51:36
举报
文章被收录于专栏:Linux云计算网络Linux云计算网络

本题和上题一样同属于层次遍历,不同的是本题从底层往上遍历,如下:

代码如下:

 1 struct TreeNode {
 2     int            val;
 3     TreeNode*    left;
 4     TreeNode*    right;
 5     TreeNode():val(0),left(NULL),right(NULL){}
 6     TreeNode(int x): val(x), left(NULL),right(NULL) {}
 7 };
 8 
 9 vector<vector<int> > levelOrderTraversalII(TreeNode *root) //非递归的中序遍历(用栈实现)
10 {
11 
12     queue<TreeNode *> tree_queue;
13     vector<vector<int> > tree_vector, tree_rvector;
14     vector<int> svector;
15     int nCount = 0;
16 
17     if (NULL == root) {
18         return tree_vector;
19     }
20     TreeNode *pTemp = root;
21     tree_queue.push(root);
22     tree_queue.push(NULL); //the end of one level.
23 
24     while (true) {
25         TreeNode *pTemp = tree_queue.front();
26         tree_queue.pop();
27 
28         if (!pTemp) { //get the null, put vector<> to vector<vector<>>
29             tree_vector.push_back(svector);
30             nCount ++;
31             svector.clear();
32             if (tree_queue.empty())
33                 break;
34             tree_queue.push(NULL);
35         }
36         else {
37             svector.push_back(pTemp->val);
38             if (pTemp->left) 
39                 tree_queue.push(pTemp->left);
40             if (pTemp->right)
41                 tree_queue.push(pTemp->right);
42         }
43     }
44     while (nCount > 0){
45         svector = tree_vector.at(nCount - 1);
46         tree_rvector.push_back(svector);
47         nCount --;
48     }
49     return tree_rvector;
50 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2014-11-27 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档