[144] 二叉树的前序遍历

给定一个二叉树，返回它的 前序 遍历。

示例:

输入: [1,null,2,3]

输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

非常典型的先序遍历树问题，有两种解法，递归与迭代。

递归法

递归写起来非常简单，遵循中-左-右的顺序即可

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

  const res: Array<number> = [];
  helper(root);

  return res;

  function helper(node: TreeNode | null): void {
    if (!node) return;

    res.push(node.val);
    helper(node.left);
    helper(node.right);
  }
}

迭代法

迭代先序遍历利用了栈的特性，直接先将根节点入栈，然后开始循环：出栈一个元素，存储节点值，若该节点有右节点，入栈，若该节点有左节点，入栈。直到栈空为止。

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

  const res: Array<number> = [];

  const stack: TreeNode[] = [root];

  while(stack.length > 0) {
    const node = stack.pop();
    res.push(node.val);
    node.right && stack.push(node.right);
    node.left && stack.push(node.left);
  }
  return res;
}

数的前中后序遍历方法相关题目：

[94] Binary Tree Inorder Traversal

[144] Binary Tree Preorder Traversal

[145] Binary Tree Postorder Traversal