Lt589. N 叉树的前序遍历

589. N 叉树的前序遍历

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

返回其前序遍历: [1,3,5,6,2,4]。

**说明: **递归法很简单，你可以使用迭代法完成此题吗?

思路

递归

按题意递归即可

迭代

借助栈完成前序遍历

解答

递归

/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node} root
 * @return {number[]}
 */
var preorder = function (root) {
  if (!root) return [];
  return [root.val, ...root.children.map((e) => preorder(e)).flat()];
};

迭代

/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node} root
 * @return {number[]}
 */
var preorder = function (root) {
  if (!root) return [];
  const res = [];
  const stack = [];
  stack.push(root);
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);
    if (node.children.length) stack.push(...node.children.reverse());
  }
  return res;
};