Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
点击打开原题链接
跟从上往下层次遍历一样，最后把结果倒置一下就可以了~~
struct node
{
TreeNode* tn;
int level;
};
class Solution
{
public:
vector
> levelOrderBottom(TreeNode *root)
{
vector
> vvi; vector
vi; deque
di; node nd; int level = 0; if (root == NULL) { return vvi; } nd.level = 0; nd.tn = root; di.push_back(nd); node left,right; while (!di.empty()) { nd = di.front(); if (nd.tn->left != NULL) { left.tn = nd.tn->left; left.level = nd.level+1; di.push_back(left); } if (nd.tn->right != NULL) { right.tn = nd.tn->right; right.level = nd.level + 1; di.push_back(right); } // if (vi.empty()) // { // vi.push_back(nd.tn->val); // level++; // di.pop_front(); // } // else // { nd = di.front(); if (nd.level == level) { vi.push_back(nd.tn->val); di.pop_front(); } else { vvi.push_back(vi); vi.clear(); vi.push_back(nd.tn->val); level++; di.pop_front(); } // } } vvi.push_back(vi); return vector
>(vvi.rbegin(),vvi.rend()); } };