zhangdizhangdi

129.求根节点到叶节点数字之和

题目

LeetCode 中等

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的所有数字之和。
叶节点 是指没有子节点的节点。

示例
输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

题解

方法：深度优先

DFS 递归 O(n) O(n)

ts
function sumNumbers(root: TreeNode | null): number {
  let sum = 0
  let path = []
  const dfs = (root: TreeNode) => {
    path.push(root.val)
    if (!root.left && !root.right) {
      sum += parseInt(path.join(''))

      console.log('到叶子节点', path)
    }
    if (root.left) dfs(root.left)
    if (root.right) dfs(root.right)
    path.pop()

    console.log('path after pop', path)
  }
  dfs(root)
  return sum
}

const tree = new Tree([4, 9, 0, 5, 1])
console.log('🌰', sumNumbers(tree.root))

方法：广度优化【todo⌛️】