n叉数的前序遍历

[chiyan-lin]

遍历法

var preorder = function(root) {
  let result = [], current = root;
  while(current){
    // 先入栈
    result.push(current.val);
    // 获取当前子节点
    let temp = current.children;
    if(!temp.length) return result;
    // 取出子节点第一位
    current = current.children.shift();
    let next = current;
    // 遍历子节点，借用相对三层的最右节点挂载相对二层的节点
    // 目的是为了处理非递归下无法回溯的问题
    while (next.children.length) {
      next = next.children[next.children.length - 1];
    }
    next.children = temp;
  }
  return result;
}

递归法

var preorder = function (root) {
  var output = []
  function order(node) {
    node.val && output.push(node.val)
    node.children && node.children.forEach(child => {
      order(child)
    })
  }
  order(root)
  return output
}

var preorder = function (root) {
  if (!root) return [];
  return Array.prototype.concat.apply([root.val], root.children.map(child => preorder(child)))
};