589.n-ary-tree-preorder-traversa
2020-05-20 本文已影响0人
Optimization
递归
class Solution {
public:
vector<int> preorder(Node* root) {
if(root == nullptr) return {};
vector<int> ans;
preorder(root, ans);
return ans;
}
private:
void preorder(Node* root, vector<int>& ans){
if(root == nullptr) return;
ans.push_back(root->val);
for(auto n: root->children){
preorder(n,ans);
}
}
};
迭代
用到了栈,反向迭代器
class Solution {
public:
vector<int> preorder(Node* root) {
// 方法:一个就是队列,一个就是栈
if(!root) return {};
stack<Node*> s;
s.push(root);
vector<int> ans;
while(!s.empty()){
Node* curNode = s.top();s.pop();
ans.push_back(curNode->val);
for(auto n_iter= curNode->children.rbegin();n_iter != curNode->children.rend(); n_iter++){
s.push(*n_iter);
}
}
return ans;
}
};