129. 求根节点到叶节点数字之和
题目描述
输入二叉树的根节点 root，每个节点上是一个 0 到 9 的数字。
从根走到某个叶子（没有孩子的节点），把沿途的数字按顺序拼起来，就得到一个整数。比如路径 1 -> 2 -> 3 对应 123。
把每条根到叶子路径对应的整数加起来，返回总和。数据保证答案在 32 位整数范围内。树用层序数组表示。
示例 1
输入：root = [1,2,3] 输出：25
解释：两条路径分别是 12 和 13，和为 25。
示例 2
输入：root = [4,9,0,5,1] 输出：1026
解释：三条路径分别是 495、491、40，和为 1026。
数据范围
- 节点总数在
[1, 1000]之间。 0 <= Node.val <= 9- 树的深度不超过
10。
解题思路：深度优先搜索
深度优先搜索，把“到目前为止拼出的数”cur 往下传。进入节点时 cur = cur*10 + val，相当于在右边补一位数字。到达叶子时 cur 就是一个完整的数，返回它；非叶子返回左右两侧之和。
为什么正确
dfs(node, cur) 返回以 node 为根的子树中，所有“前缀 cur 接上子树内路径”所代表的数之和。
复杂度分析
时间 O(n)，空间 O(h)。
易错点
只在叶子处返回 cur；空节点必须返回 0 而不是 cur，否则只有一侧孩子的节点会把半截数字也算进去。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
def dfs(node, cur):
if not node:
return 0
cur = cur * 10 + node.val
if not node.left and not node.right:
return cur
return dfs(node.left, cur) + dfs(node.right, cur)
return dfs(root, 0)class Solution {
int dfs(TreeNode node, int cur) {
if (node == null) {
return 0;
}
cur = cur * 10 + node.val;
if (node.left == null && node.right == null) {
return cur;
}
return dfs(node.left, cur) + dfs(node.right, cur);
}
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
}class Solution {
public:
int dfs(TreeNode* node, int cur) {
if (!node) {
return 0;
}
cur = cur * 10 + node->val;
if (!node->left && !node->right) {
return cur;
}
return dfs(node->left, cur) + dfs(node->right, cur);
}
int sumNumbers(TreeNode* root) {
return dfs(root, 0);
}
};func sumNumbers(root *TreeNode) int {
var dfs func(node *TreeNode, cur int) int
dfs = func(node *TreeNode, cur int) int {
if node == nil {
return 0
}
cur = cur*10 + node.Val
if node.Left == nil && node.Right == nil {
return cur
}
return dfs(node.Left, cur) + dfs(node.Right, cur)
}
return dfs(root, 0)
}var sumNumbers = function(root) {
const dfs = (node, cur) => {
if (!node) {
return 0;
}
cur = cur * 10 + node.val;
if (!node.left && !node.right) {
return cur;
}
return dfs(node.left, cur) + dfs(node.right, cur);
};
return dfs(root, 0);
};function sumNumbers(root: TreeNode | null): number {
const dfs = (node: TreeNode | null, cur: number): number => {
if (!node) {
return 0;
}
cur = cur * 10 + node.val;
if (!node.left && !node.right) {
return cur;
}
return dfs(node.left, cur) + dfs(node.right, cur);
};
return dfs(root, 0);
}其他解法
两种解法都访问每个节点一次；深度优先搜索空间随树高变化，广度优先搜索空间随树宽变化。
解法 2：广度优先搜索 时间 O(n)，空间 O(w)
队列中存放（节点，从根到该节点组成的数）。弹出节点时，如果是叶子就把数加入总和。否则对每个孩子入队，数变成 num × 10 + child.val。
没有递归，树很深时不会栈溢出。队列要同时保存节点和当前数，代码比递归长。
from collections import deque
from typing import Optional
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
total = 0
q = deque([(root, root.val)])
while q:
node, num = q.popleft()
if not node.left and not node.right:
total += num
if node.left:
q.append((node.left, num * 10 + node.left.val))
if node.right:
q.append((node.right, num * 10 + node.right.val))
return totalclass Solution {
public int sumNumbers(TreeNode root) {
if (root == null) return 0;
int total = 0;
Deque<TreeNode> nodes = new ArrayDeque<>();
Deque<Integer> nums = new ArrayDeque<>();
nodes.offer(root);
nums.offer(root.val);
while (!nodes.isEmpty()) {
TreeNode node = nodes.poll();
int num = nums.poll();
if (node.left == null && node.right == null) total += num;
if (node.left != null) {
nodes.offer(node.left);
nums.offer(num * 10 + node.left.val);
}
if (node.right != null) {
nodes.offer(node.right);
nums.offer(num * 10 + node.right.val);
}
}
return total;
}
}class Solution {
public:
int sumNumbers(TreeNode* root) {
if (!root) return 0;
int total = 0;
queue<pair<TreeNode*, int>> q;
q.push({root, root->val});
while (!q.empty()) {
auto [node, num] = q.front();
q.pop();
if (!node->left && !node->right) total += num;
if (node->left) q.push({node->left, num * 10 + node->left->val});
if (node->right) q.push({node->right, num * 10 + node->right->val});
}
return total;
}
};func sumNumbers(root *TreeNode) int {
if root == nil {
return 0
}
type item struct {
node *TreeNode
num int
}
total := 0
q := []item{{root, root.Val}}
for len(q) > 0 {
cur := q[0]
q = q[1:]
node, num := cur.node, cur.num
if node.Left == nil && node.Right == nil {
total += num
}
if node.Left != nil {
q = append(q, item{node.Left, num*10 + node.Left.Val})
}
if node.Right != nil {
q = append(q, item{node.Right, num*10 + node.Right.Val})
}
}
return total
}var sumNumbers = function(root) {
if (!root) return 0;
let total = 0;
const q = [[root, root.val]];
for (let head = 0; head < q.length; head++) {
const [node, num] = q[head];
if (!node.left && !node.right) total += num;
if (node.left) q.push([node.left, num * 10 + node.left.val]);
if (node.right) q.push([node.right, num * 10 + node.right.val]);
}
return total;
};function sumNumbers(root: TreeNode | null): number {
if (!root) return 0;
let total = 0;
const q: [TreeNode, number][] = [[root, root.val]];
for (let head = 0; head < q.length; head++) {
const [node, num] = q[head];
if (!node.left && !node.right) total += num;
if (node.left) q.push([node.left, num * 10 + node.left.val]);
if (node.right) q.push([node.right, num * 10 + node.right.val]);
}
return total;
}