589. N叉树的前序遍历——easy

给定一个 N 叉树，返回其节点值的前序遍历。
例如，给定一个 3叉树 :

返回其前序遍历: [1,3,5,6,2,4]。
说明: 递归法很简单，你可以使用迭代法完成此题吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal

思路：
迭代版：前序遍历的顺序是 [根,儿子].使用数组来模拟栈，来得到前序遍历。首先将根节点入栈，根节点是前序遍历中的第一个节点，然后从取出栈顶元素u，例如 u 的子节点从左到右为v1，v2，v3。因为栈的FILO的特点，需要逆序子节点以v3，v2，v1的顺序入栈，保证按照正确的出栈顺序：v1，v2，v3。
递归版：看代码吧。
复杂度分析：
时间复杂度O(n)
空间复杂度O(n)

//迭代版
var preorder = function (root) {
    let ans = [];
    if (root == null) {
        return ans;
    }
    let stack = [];
    stack.push(root);
    while (stack.length) {
        let node = stack.pop();
        ans.push(node.val);
        // Collections.reverse(node.children);
        node.children.reverse();
        for (let item of node.children) {
            stack.push(item);
        }
    }
    return ans;
};
//递归版
var preorder = function (root) {
    let ans = [];
    const dfs = (root) => {
        if (root === null) return;
        ans.push(root.val);
        for (let item of root.children) {
            dfs(item);
        }
    };
    dfs(root);
    return ans;
};