Skip to content

590 N-ary Tree Postorder Traversal¶

Given an n-ary tree, return the postorder traversal of its nodes’ values.

For example, given a 3-ary tree: alt

Return its postorder traversal as: [5,6,3,2,4,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1: Recursive¶

// 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¶

// 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;
  }
};

1. N-ary Tree Preorder Traversal
1. Binary Tree Postorder Traversal
1. Binary Tree Level Order Traversal