本题和上题一样同属于层次遍历,不同的是本题从底层往上遍历,如下:
代码如下:
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 }