Problem
Given an n-ary tree, return the preorder traversal of its nodes’ values.
For example, given a 3-ary tree:
Return its preorder traversal as: [1,3,5,6,2,4].
Note: Recursive solution is trivial, could you do it iteratively?
Solution1: Recursive
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 48 ms class Solution { public: vector<int> preorder(Node* root) { vector<int> ans; preorder(root, ans); return ans; } private: void preorder(Node* root, vector<int>& ans) { if (!root) return; ans.push_back(root->val); for (const auto& child : root->children) preorder(child, ans); } }; |
Solution2: Iterative
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua // Running time: 52 ms class Solution { public: vector<int> preorder(Node* root) { if (!root) return {}; vector<int> ans; stack<Node*> s; s.push(root); while (!s.empty()) { const Node* node = s.top(); s.pop(); ans.push_back(node->val); for (auto it = node->children.rbegin(); it != node->children.rend(); ++it) s.push(*it); } return ans; } }; |
Related Problems
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment