https://leetcode.com/problems/binary-tree-level-order-traversal-ii/#/description
这题不难主要贴出使用vector和queue的两种算法(利用queue思路比较巧妙同时也比前者快)。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> vecResult;
vector<vector<int>> res = coutVec0(root, 0, vecResult);
reverse(res.begin(), res.end());
return res;
}
vector<vector<int>> coutVec0(TreeNode* root,int level ,vector<vector<int>>& vecResult){
if(!root){
return vecResult;
}
if(level < vecResult.size()){
// vecResult[vecResult.size()-1-level].push_back(root->val);
vecResult[level].push_back(root->val);
}else if(level == vecResult.size()){
vector<int> vec;
vec.push_back(root->val);
// vecResult.insert(vecResult.begin(), vec);
vecResult.push_back(vec);
}
++level;
coutVec0(root->left, level, vecResult);
coutVec0(root->right, level, vecResult);
return vecResult;
}
};
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
if (!root) {
return res;
}
queue<TreeNode*> t;
t.push(root);
while (!t.empty()) { //将"某一层"的节点的子节点都放到队列中,并把原来的节点出列
vector<int> tn;
int cnt = t.size();
for (unsigned int i = 0; i < cnt; ++i) {
TreeNode *cur = t.front();
tn.push_back(cur->val);
t.pop();
if (cur->left)
t.push(cur->left);
if (cur->right)
t.push(cur->right);
}
//do not use insert() here,it cost too much time.
//use reverse() insteadly
res.push_back(tn);
}
reverse(res.begin(), res.end());
return res;
}
网友评论