{"id":3113,"date":"2018-07-12T23:24:56","date_gmt":"2018-07-13T06:24:56","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3113"},"modified":"2018-09-04T02:14:54","modified_gmt":"2018-09-04T09:14:54","slug":"leetcode-590-n-ary-tree-postorder-traversal","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-590-n-ary-tree-postorder-traversal\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 590. N-ary Tree Postorder Traversal"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given an n-ary tree, return the\u00a0postorder<\/i>\u00a0traversal of its nodes’ values.<\/p>\n

 <\/p>\n

For example, given a\u00a03-ary<\/code>\u00a0tree:<\/p>\n

<\/p>\n

 <\/p>\n

Return its postorder traversal as:\u00a0[5,6,3,2,4,1]<\/code>.<\/p>\n

 <\/p>\n

Note:<\/b>\u00a0Recursive solution is trivial, could you do it iteratively?<\/p>\n

\u00a0<\/ins><\/p>\n

Solution 1: Recursive<\/strong><\/h1>\n
\n

C++<\/h2>\n
\n\n
\/\/ Author: Huahua\r\n\/\/ Running time: 44 ms\r\nclass Solution {\r\npublic:\r\n  vector<int> postorder(Node* root) {\r\n    vector<int> ans;\r\n    postorder(root, ans);\r\n    return ans;\r\n  }\r\nprivate:\r\n  void postorder(Node* root, vector<int>& ans) {\r\n    if (!root) return;\r\n    for (auto child : root->children)\r\n      postorder(child, ans);\r\n    ans.push_back(root->val);\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n
Solution 2: Iterative<\/strong><\/h1>\n
\n
C++<\/h2>\n
\n\n
\/\/ Author: Huahua\r\n\/\/ Running time: 44 ms\r\nclass Solution {\r\npublic:\r\n  vector<int> postorder(Node* root) {\r\n   if (!root) return {};\r\n    vector<int> ans;\r\n    stack<Node*> s;\r\n    s.push(root);\r\n    while (!s.empty()) {\r\n      const Node* node = s.top(); s.pop();      \r\n      ans.push_back(node->val);\r\n      for (auto child : node->children)\r\n        s.push(child);      \r\n    }\r\n    reverse(begin(ans), end(ans));\r\n    return ans;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n
Related Problems<\/strong><\/h1>\n