Recurisve:
/* // 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> order = {}; if (root) { traversal(root, order); } return order; } void traversal(Node* root, vector<int> &order) { int num = root->children.size(); for (int i = 0; i < num; i++) { traversal(root->children.at(i), order); } order.push_back(root->val); } };
Iteratve:
/* // 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> order = {}; map<Node*, bool> visit; stack<Node*> nodeStack; if (root) { nodeStack.push(root); } while (!nodeStack.empty()) { Node* node = nodeStack.top(); int num = node->children.size(); if (num > 0 && visit.find(node) == visit.end()) { for (int i = num - 1; i >= 0 ; i--) { nodeStack.push(node->children.at(i)); } visit[node] = true; } else { order.push_back(node->val); nodeStack.pop(); } } return order; } };