589. Antecedent traversal of N fork trees

The title

Given an n-tree, returns a sequential traversal of its node values.

The n-fork tree is serialized in the input as a sequential traversal, with each set of child nodes separated by null values (see example).

Advanced:

Recursion is easy. Can you do it iteratively?

Example 1

Input: root = [1, null, 3 4-trichlorobenzene, null, 5, 6] output:,3,5,6,2,4 [1]Copy the code

Their thinking

The recursive method

Depth-first traversal, traversing the root node, recursively traversing the left subtree, recursively traversing the right subtree

code

var preorder = function (root) {
  let result = []
  helper(root)
  return result
  function helper(node) {
    if(! node)return
    result.push(node.val)
    const len = (node.children || []).length
    for (let i = 0; i < len; i++) {
      helper(node.children[i])
    }
  }
}
Copy the code

Iterative method

Push the n-tree onto the stack, and push N nodes of the n-tree in turn on the stack;

Dynamic figure

code

var preorder = function (root) {
  if (root === null) return []
  let result = []
  let stack = [root]
  while (stack.length) {
    const node = stack.pop()
    result.push(node.val)
    const len = (node.children || []).length
    for (let i = len - 1; i >= 0; i--) {
      stack.push(node.children[i])
    }
  }
  return result
}

Copy the code