先序遍历二叉树的三种方法

最近温故了二叉树的相关算法，根据 labuladong 的算法小抄学习了二叉树数据结构的一个框架，结合以前跟着 B 站清华大学数据结构精品课学习的迭代的方式遍历二叉树，一共总结了三种先序遍历二叉树的方法，特此记录。

traverse 遍历方法

思路是利用递归函数遍历一个二叉树，但是遍历的过程中，并不会有返回值，所以可以利用一个外部变量（或者形参）来记录遍历的结果。

function preorderTraversal(root: TreeNode | null): number[] {
  const res = [];

  function traverse(root: TreeNode | null) {
    if (!root) return;

    res.push(root.val);
    traverse(root.left);
    traverse(root.right);
  }

  traverse(root);

  return res;
}

分解子问题，并利用子问题的解得到全局的解

这个方法和遍历法最重要的区别就是，需要利用函数的返回值，然后在后序遍历的位置，拼装结果。
思路是在递归的过程中，先将跟节点的值放入结果中，然后算出左子树的结果，然后算出右子树的结果，最后把左右子树的结果按顺序拼接到根节点的结果当中。最后返回。

function preorderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];

  const res = [];

  // 访问根节点
  res.push(root.val);

  // 计算左右子树的结果
  const left = preorderTraversal(root.left);
  const right = preorderTraversal(root.right);

  // 拼接左子树
  res.push(...left);
  // 拼接右子树
  res.push(...right);

  return res;
}

迭代的方式

思路是利用一个数组来模拟函数的调用栈，在迭代的过程中，先访问跟节点，然后访问左子树，在访问的过程中，如果有有右子树就入栈。

function preorderTraversal(root: TreeNode | null): number[] {
  if (!root) return [];

  const res = [];
  const nodes = [root];

  while (nodes.length) {
    let node = nodes.pop();
    while (node) {
      res.push(node.val);

      if (node.right) nodes.push(node.right);

      node = node.left;
    }
  }

  return res;
}