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