【leetcode】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:

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

Note:

Recursive solution is trivial, could you do it iteratively?

1. Recursive solution:

/*

// 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> preorder(Node* root) {

        vector<int> order = {};

        if (root) {

            traversal(root, order);

        }

        return order;

    }

    void traversal(Node* root, vector<int> &order) {

        order.push_back(root->val);

        int num = root->children.size();

        for (int i = 0; i < num; i++) {

            traversal(root->children.at(i), order);

        }

    }

};

2. Iterative solution:

/*

// 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> preorder(Node* root) {

        vector<int> order = {};

        stack<Node*> nodeStack;

        if (root) {

            nodeStack.push(root);

        }

        while (!nodeStack.empty()) {

            Node* node = nodeStack.top();

            nodeStack.pop();

            order.push_back(node->val);

            int num = node->children.size();

            for (int i = num - 1; i >= 0; i--) {

                nodeStack.push(node->children.at(i));

            }

        }

        return order;

    }

};

巴特西

【leetcode】589. N-ary Tree Preorder Traversal

最新文章

热门文章