Binary Tree Level Order Traversal II
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]
]
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1
/ \
2 3
/
4
\
5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
解法一：递归
参考了Discussion中stellari的做法，递归进行层次遍历，并将每个level对应于相应的vector。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
vector<vector<int> > result; void levelTra(TreeNode *root, int level)
{
if(root == NULL)
return;
if(level == result.size())
{
vector<int> v;
result.push_back(v);
}
result[level].push_back(root->val);
levelTra(root->left, level+);
levelTra(root->right, level+);
} vector<vector<int> > levelOrderBottom(TreeNode *root)
{
levelTra(root, );
return vector<vector<int> >(result.rbegin(), result.rend());
}
};
解法二：普通层次遍历后逆序。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/ struct Node
{
TreeNode* tNode;
int level;
Node(TreeNode* newtNode, int newlevel): tNode(newtNode), level(newlevel) {}
}; class Solution {
public:
vector<vector<int> > levelOrderBottom(TreeNode *root) {
vector<vector<int> > ret;
if(!root)
return ret;
// push root
Node* rootNode = new Node(root, );
queue<Node*> Nqueue;
Nqueue.push(rootNode); vector<int> cur;
int curlevel = ;
while(!Nqueue.empty())
{
Node* frontNode = Nqueue.front();
Nqueue.pop(); if(frontNode->level > curlevel)
{
ret.push_back(cur);
cur.clear();
curlevel = frontNode->level;
} cur.push_back(frontNode->tNode->val); if(frontNode->tNode->left)
{
Node* leftNode = new Node(frontNode->tNode->left, frontNode->level+);
Nqueue.push(leftNode);
}
if(frontNode->tNode->right)
{
Node* rightNode = new Node(frontNode->tNode->right, frontNode->level+);
Nqueue.push(rightNode);
}
}
ret.push_back(cur); reverse(ret.begin(), ret.end());
return ret;
}
};