589. N 叉树的前序遍历

题目

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

N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

例

输入：root = [1,null,3,2,4,null,5,6]

输出：[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 [];
  let res = [];
  function NPO(node) {
    if (!node) return;
    res.push(node.val);
    for (let c of node.children) {
      if (c) NPO(c);
    }
  }
  NPO(root);
  return res;
};

迭代

/**
 * // 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 [];
  let res = [];
  let s = [root];
  while (s.length) {
    let node = s.pop();
    res.push(node.val);
    if (node.children)
      for (let i = node.children.length - 1; i >= 0; i--) {
        let c = node.children[i];
        if (c) s.push(c);
      }
  }

  return res;
};