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