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

Categories:

Tags:

题目描述
思路分析
1. 解法一：DFS 前序遍历（推荐）
相似题目

题目描述

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

思路分析

解法一：DFS 前序遍历（推荐）

核心思路：

用 DFS 前序遍历，携带当前路径形成的数字 cur 向下传递：

每到一个节点，cur = cur * 10 + node.val（将当前节点值追加到数字末尾）

到达叶子节点（左右子节点均为空）时，将 cur 累加到结果

递归处理左右子树

举例：树 [1, 2, 3]

根 1：cur = 1

左 2：cur = 12（叶子），累加 12

右 3：cur = 13（叶子），累加 13

结果 = 25

复杂度分析：

时间复杂度：O(n)，其中 n 为节点数，每个节点恰好访问一次

空间复杂度：O(h)，其中 h 为树的高度，递归栈深度

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private 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);
    }
}

func sumNumbers(root *TreeNode) int {
	var res int
	var dfs func(node *TreeNode, cur int)
	dfs = func(node *TreeNode, cur int) {
		if node == nil {
			return
		}
		// 将当前节点值追加到路径数字末尾
		cur = cur*10 + node.Val
		// 到达叶子节点，加入结果
		if node.Left == nil && node.Right == nil {
			res += cur
			return
		}
		dfs(node.Left, cur)
		dfs(node.Right, cur)
	}
	dfs(root, 0)
	return res
}

相似题目

题目	难度	考察点
112. 路径总和	简单	DFS 路径求和判断
113. 路径总和 II	中等	DFS 记录所有路径
257. 二叉树的所有路径	简单	DFS 记录路径字符串
437. 路径总和 III	中等	前缀和+DFS
404. 左叶子之和	简单	DFS 标记左叶子
124. 二叉树中的最大路径和	困难	DFS 路径最大值

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/06191313