Leetcode 590. N-ary Tree Postorder Traversal

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

• Recursive

/* // Definition for a Node. class Node { public:int val;vector<Node*> children;Node() {}Node(int _val, vector<Node*> _children) {val = _val;children = _children;} }; */
class Solution {
public:vector<int> postorder(Node* root) {vector<int> result;if(!root) {return result;}postOrderTraverse(result, root);return result;}void postOrderTraverse(vector<int>& result, Node* root) {if(!root) {return;}int size = root->children.size();for(int i = 0; i < size; i++) {postOrderTraverse(result, root->children[i]);}result.push_back(root->val);}
};

• Iterative

/* // Definition for a Node. class Node { public:int val;vector<Node*> children;Node() {}Node(int _val, vector<Node*> _children) {val = _val;children = _children;} }; */
class Solution {
public:vector<int> postorder(Node* root) {vector<int> result;if(!root) {return result;}postOrderTraverse(result, root);return result;}void postOrderTraverse(vector<int>& result, Node* root) {stack<Node*> list;list.push(root);while(!list.empty()) {Node* current = list.top();list.pop();int size = current->children.size();for(int i = 0; i < size; i++) {list.push(current->children[i]);}result.push_back(current->val);}reverse(result.begin(), result.end());}
};

Reference

1. https://leetcode.com/problems/n-ary-tree-postorder-traversal/description/