Skip to content

589 N-ary Tree Preorder Traversal¶

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

For example, given a 3-ary tree: alt

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

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

Solution1: Recursive¶

// Running time: 48 ms
class Solution {
public:
  vector<int> preorder(Node* root) {
    vector<int> ans;
    preorder(root, ans);
    return ans;
  }
private:
  void preorder(Node* root, vector<int>& ans) {
    if (!root) return;
    ans.push_back(root->val);
    for (const auto& child : root->children)
      preorder(child, ans);
  }
};

Solution2: Iterative¶

// Running time: 52 ms
class Solution {
public:
  vector<int> preorder(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 it = node->children.rbegin(); it != node->children.rend(); ++it)
        s.push(*it);
    }
    return ans;
  }
};

1. N-ary Tree Postorder Traversal
1. Verify Preorder Serialization of a Binary Tree