[LeetCode] 589. N-ary Tree Preorder Traversal

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

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: [1,3,5,6,2,4]

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

Constraints:
The number of nodes in the tree is in the range [0, 104].
0 <= Node.val <= 104
The height of the n-ary tree is less than or equal to 1000.

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

N叉树的前序遍历。

给定一个 n 叉树的根节点 root ，返回 其节点值的 前序遍历 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题目的 followup 问能不能用迭代的做法做。我这里给出迭代和递归的两种不同做法。其中迭代是 DFS 做的。

迭代复杂度

时间O(n)
空间O(n)

迭代代码

Java实现

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        // corner case
        if (root == null) {
            return res;
        }

        // normal case
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            for (int i = cur.children.size() - 1; i >= 0; i--) {
                stack.push(cur.children.get(i));
            }
            res.add(cur.val);
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {Node} root
 * @return {number[]}
 */
var preorder = function (root) {
    let res = [];
    // corner case
    if (root === null) {
        return res;
    }

    // normal case
    let stack = [root];
    while (stack.length) {
        let cur = stack.pop();
        let size = cur.children.length;
        for (let i = size - 1; i >= 0; i--) {
            stack.push(cur.children[i]);
        }
        res.push(cur.val);
    }
    return res;
};

递归复杂度

时间O(n)
空间O(n)

递归代码

Java实现

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        // corner case
        if (root == null) {
            return res;
        }
        helper(root, res);
        return res;
    }

    private void helper(Node root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        for (Node child : root.children) {
            helper(child, res);
        }
    }
}

JavaScript实现

/**
 * @param {Node} root
 * @return {number}
 */
var preorder = function (root) {
    let res = [];
    if (root === null) {
        return res;
    }
    helper(res, root);
    return res;
};

var helper = function (res, root) {
    if (root === null) {
        return;
    }
    res.push(root.val);
    for (let child of root.children) {
        helper(res, child);
    }
};