力扣链接：129.求根节点到叶节点数字之和

难度：⭐⭐

✏️ 方法一：

解题关键词：二叉树、递归

解题思路：使用深度优先遍历，然后记录一个 preSum，如果是叶子节点，那么直接将 preSum + 叶子节点的值返回，否则继续向下深度遍历。

function sumNumbers(root: TreeNode | null): number {
  // 深度优先遍历
  const dfs = (root: TreeNode | null, preSum: number): number => {
    // 如果节点为空，返回0
    if (root === null) return 0

    // 将当前节点的值 + 前面和*10
    const sum = preSum * 10 + root.val
    // 如果是叶子节点，直接返回和
    if (root.left === null && root.right === null) return sum

    // 不是叶子节点，一直向下递归
    return dfs(root.left, sum) + dfs(root.right, sum)
  }

  const sum = dfs(root, 0)

  return sum
};

✏️ 方法二：

解题关键词：二叉树、栈

解题思路：使用两个栈，一个栈保存节点，另一个栈保存对应节点的数字，如果遇到叶子节点，那么将此时节点对应的数值加到 result 上，如果不是叶子节点，继续把左右孩子节点入栈，并且将左右孩子对应的数字也入栈。

function sumNumbers(root: TreeNode | null): number {
  // 如果 root 为空，直接返回0
  if (root === null) return 0

  // 最后的结果
  let result = 0
  // 存放节点的队列
  const queue: TreeNode[] = [root]
  // 存放上面队列中每个节点对应的数字
  const pathSum: number[] = [root.val]

  while (queue.length) {
    // 每个节点出对
    const target = queue.shift()
    // 拿出当前节点对应的数字
    const sum = pathSum.shift()!

    // 如果是叶子节点，加到 result
    if (target.left === null && target.right === null) {
      result += sum
    }

    // 判断左节点是否存在，存在的话入队，并且将节点对应的数字入队
    if (target.left) {
      queue.push(target.left)
      pathSum.push(sum * 10 + target.left.val)
    }
    // 判断右节点是否存在，存在的话入队，并且将节点对应的数字入队
    if (target.right) {
      queue.push(target.right)
      pathSum.push(sum * 10 + target.right.val)
    }
  }

  return result
};