N叉树的常见遍历算法

如图给定一个 N 叉树，返回其节点值的遍历。假设节点的结构如下：

interface INode {
  val: number;
  children?: INode[];
}

前序遍历

预期遍历结果：[1,3,5,6,2,4]

function preorder(root: INode | null): number[] {
  let result: number[] = [];

  if (!root) {
    return [];
  }

  const { val, children = [] } = root;

  result.push(val);

  children.forEach((child) => {
    result = result.concat(preorder(child));
  });

  return result;
}

后序遍历

预期遍历结果：[5,6,3,2,4,1]

function postorder(root: INode | null): number[] {
  let result: number[] = [];

  if (!root) {
    return [];
  }

  const { val, children = [] } = root;

  children.forEach((child) => {
    result = result.concat(postorder(child));
  });

  result.push(val);

  return result;
}

层序遍历

预期遍历结果：[[1],[3,2,4],[5,6]]

function levelOrder(root: INode | null): number[][] {
  const result: number[][] = [];

  if (!root) {
    return [];
  }

  const traversal = function (node: INode, depth: number) {
    if (!result[depth]) {
      result[depth] = [];
    }

    const { val, children = [] } = node;

    result[depth].push(val);

    children.forEach((child) => {
      traversal(child, depth + 1);
    });
  };

  traversal(root, 0);

  return result;
}