[LeetCode] 589. N-ary Tree Preorder Traversal

Easy

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

For example, given a 3-ary tree:

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

Note:

Recursive solution is trivial, could you do it iteratively?

题目大意：n-ary数是根节点可拥有n个子节点的树，比如一个3-ary树如图所示。求出n-ary树的前序遍历。

前序遍历：根节点->左子树->右子树

方法一：递归

递归的将节点的值存入结果向量中

代码如下：

class Solution {
public:
    vector<int> preorder(Node* root) {
        if (!root)return {};
        vector<int> res;
        res.push_back((*root).val);
    　　if (!(*root).children.empty()) {
        　　int len = ((*root).children).size();
        　　for (int i = 0; i < len; ++i) {
            　　vector<int> temp = preorder((*root).children[i]);
            　　res.insert(res.end(), temp.begin(), temp.end());
        　　}
    　　}
        return res;
    }
};

方法二：迭代法

使用堆来记录节点，然后逐个节点深入。这里要注意的是，因为是前序排列，所以要按照右子树->左子树的顺序将各节点放入stack中。

代码如下：

class Solution {
public:
    vector<int> preorder(Node* root) {
        if (!root)return {};
        vector<int> res;
        stack<Node*> s;
        s.push(root);
        while (!s.empty()) {
            Node* temp = s.top();
            res.push_back(s.top()->val);
            s.pop();
            int len = temp->children.size();
            for (int i = len-1; i >= 0; --i) {
                s.push(temp->children[i]);
            }
        }
        return res;
    }
};

ps一点个人想法：逐层遍历时使用queue更方便，其他时候使用stack。