力扣原题：589. N叉树的前序遍历

解题

递归

  1. /**
  2.  * // Definition for a Node.
  3.  * function Node(val, children) {
  4.  *    this.val = val;
  5.  *    this.children = children;
  6.  * };
  7.  */
  9. /**
  10.  * @param {Node} root
  11.  * @return {number[]}
  12.  */
  13. var preorder = function(root) {
  14.     var res = [];
  15.     dp(root)
  16.     function dp(root) {
  17.         if (!root) return;
  18.         res.push(root.val);
  19.         for(var child of root.children) {
  20.             dp(child);
  21.         }
  22.     }
  23.     return res;
  24. };

复杂度计算

  • 时间复杂度：O(M) 其中 M 是 N 叉树中的节点个数。所有节点只需要遍历一次。

  • 空间复杂度：O(M) 其中 M 是 N 叉树中的节点个数。所有节点只需要遍历一次。

    迭代

    利用队列存储 ```javascript /**

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

/**

  • @param {Node} root
  • @return {number[]} */ var preorder = function(root) { var res = []; var stack = [root]; while(stack.length) {
    1.  const cur = stack.pop();
    2.  if (!cur) continue;
    3.  res.push(cur.val);
    4.    // 这里需要将数组反转
    5.  for(var child of cur.children.reverse()) {
    6.      stack.push(child);
    7.  }
    } return res; }; ```

    复杂度分析

  • 时间复杂度：时间复杂度：O(M)，其中 M 是 N 叉树中的节点个数。每个节点只会入栈和出栈各一次。

  • 空间复杂度：O(M)。在最坏的情况下，这棵 N 叉树只有 2 层，所有第 2 层的节点都是根节点的孩子。将根节点推出栈后，需要将这些节点都放入栈，共有 M - 1 个节点，因此栈的大小为 O(M)。