129. 求根到叶子节点数字之和Sum Root to Leaf Numbers递归 DFS 与双队列递推双解法精讲【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文以 LeetCode 129 题《求根到叶子节点数字之和》为核心系统讲解如何将从根到叶子节点的路径编码为十进制数字并求和。你会掌握一条极其优雅的递归范式helper 携带当前累计值自顶向下传递以及用两个队列把递归改写成层序递推的完整实现覆盖 JS、C、Python、Go、PHP 五种语言。该题收录于 leetcode 仓库的 problems/129.sum-root-to-leaf-numbers.md并在 SUMMARY.md 中被归类为中等难度题。题目描述给定一个二叉树它的每个结点都存放一个 0-9 的数字每条从根到叶子节点的路径都代表一个数字。例如从根到叶子节点路径 1-2-3 代表数字 123。计算从根到叶子节点生成的所有数字之和。说明: 叶子节点是指没有子节点的节点。示例 1:输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径 1-2 代表数字 12. 从根到叶子节点路径 1-3 代表数字 13. 因此数字总和 12 13 25.示例 2:输入: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 输出: 1026 解释: 从根到叶子节点路径 4-9-5 代表数字 495. 从根到叶子节点路径 4-9-1 代表数字 491. 从根到叶子节点路径 4-0 代表数字 40. 因此数字总和 495 491 40 1026.前置知识递归DFS深度优先遍历二叉树的基本遍历本题在仓库的 thinkings/DFS.md 中属于深度优先遍历专题的典型应用DFS 概念源自图论但在搜索题中一般指通过递归函数实现的暴力枚举而树的题目几乎都可以使用 DFS 解决且基于递归的实现更简洁、更不易出错。公司阿里百度字节思路携带当前累计值的自顶向下递归这是一道非常适合训练递归的题目。虽然题目不难但是要想一次写正确并且代码要足够优雅却不是很容易。核心思路是定一个递归的 helper 函数用来帮助我们完成递归操作。递归函数的功能是将它的左右子树相加注意这里不包括这个节点本身否则会多加我们其实关注的就是叶子节点的值然后通过层层回溯到 root返回即可。递归调用的关键设计如下helper 接收两个参数当前节点 node 与从根到父节点的累计数字 cur遇到空节点返回 0空节点不产生路径属于当前不是叶子节点、不计算的兜底分支用公式next cur * 10 node.val将当前节点拼接进路径数字若当前节点是叶子左右孩子均为空直接返回 next即这条根到叶子的路径完整了否则递归计算左、右子树并把两棵子树的所有叶子路径数字之和相加返回。数字拼接的计算逻辑如下图所示——每一步都是父路径数字 × 10 当前节点数字例如路径 4-9-5根节点 4到 9 得到 4×10949再到 5 得到 49×105495关键点解析递归分析明确空节点返回 0与叶子节点返回累计值两个终止条件的分工状态传递把 cur父路径累计值作为递归参数自顶向下传递避免使用全局变量回溯汇总左右子树的结果相加逐层返回给上层最终在根节点得到全部叶子路径数字之和。仓库在 assets/drawio/129.sum-root-to-leaf-numbers.drawio 中提供了本题的 draw.io 流程图可配合本文的递归调用关系对照理解。代码语言支持JSCPython, Go, PHPJS Code/* * lc appleetcode id129 langjavascript * * [129] Sum Root to Leaf Numbers */ function helper(node, cur) { if (node null) return 0; const next node.val cur * 10; if (node.left null node.right null) return next; const l helper(node.left, next); const r helper(node.right, next); return l r; } /** * Definition for a binary tree node. * function TreeNode(val) { * this.val val; * this.left this.right null; * } */ /** * param {TreeNode} root * return {number} */ var sumNumbers function (root) { // tag: tree dfs math return helper(root, 0); };C Code/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int sumNumbers(TreeNode* root) { return helper(root, 0); } private: int helper(const TreeNode* root, int val) { if (root nullptr) return 0; auto ret root-val val * 10; if (root-left nullptr root-right nullptr) return ret; auto l helper(root-left, ret); auto r helper(root-right, ret); return l r; } };Python Code:# class TreeNode: # def __init__(self, x): # self.val x # self.left None # self.right None class Solution: def sumNumbers(self, root: TreeNode) - int: def helper(node, cur_val): if not node: return 0 next_val cur_val * 10 node.val if not (node.left or node.right): return next_val left_val helper(node.left, next_val) right_val helper(node.right, next_val) return left_val right_val return helper(root, 0)Go Code/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func sumNumbers(root *TreeNode) int { return helper(root, 0) } func helper(root *TreeNode, cur int) int { if root nil { return 0 // 当前非叶子节点, 不计算 } next : cur*10 root.Val if root.Left nil root.Right nil { return next // 当前为叶子节点, 计算 } l : helper(root.Left, next) r : helper(root.Right, next) return l r }PHP Code/** * Definition for a binary tree node. * class TreeNode { * public $val null; * public $left null; * public $right null; * function __construct($value) { $this-val $value; } * } */ class Solution { /** * param TreeNode $root * return Integer */ function sumNumbers($root) { return (new Solution())-helper($root, 0); } /** * param TreeNode $root * param int $cur * return int */ function helper($root, $cur) { if (!$root) return 0; // 当前不是叶子节点 $next $cur * 10 $root-val; if (!$root-left !$root-right) return $next; // 当前为叶子节点, 返回叶子节点的值 $l (new Solution())-helper($root-left, $next); $r (new Solution())-helper($root-right, $next); return $l $r; } }复杂度分析时间复杂度$O(N)$每个节点访问一次空间复杂度$O(N)$最坏情况下树退化为链递归调用栈深度为 N平均情况下为树高 $O(\log N)$拓展用双队列将递归改写为层序递推通常来说可以利用队列、栈等数据结构将递归算法转为递推算法。递归版本依赖系统调用栈隐式保存每条路径的累计值而递推版本则用两个队列显式保存。描述使用两个队列当前和队列保存上一层每个结点的当前和比如 49 和 40结点队列保存当前层所有的非空结点每次循环按层处理结点队列。处理步骤从结点队列取出一个结点从当前和队列将上一层对应的当前和取出来若左子树非空则将该值乘以 10 加上左子树的值并添加到当前和队列中若右子树非空则将该值乘以 10 加上右子树的值并添加到当前和队列中若左右子树均为空时将该节点的当前和加到返回值中实现语言支持CPythonC Codeclass Solution { public: int sumNumbers(TreeNode* root) { if (root nullptr) return 0; auto ret 0; auto runningSum vectorint{root-val}; auto queue vectorconst TreeNode*{root}; while (!queue.empty()) { auto sz queue.size(); for (auto i 0; i sz; i) { auto n queue.front(); queue.erase(queue.begin()); auto tmp runningSum.front(); runningSum.erase(runningSum.begin()); if (n-left ! nullptr) { runningSum.push_back(tmp * 10 n-left-val); queue.push_back(n-left); } if (n-right ! nullptr) { runningSum.push_back(tmp * 10 n-right-val); queue.push_back(n-right); } if (n-left nullptr n-right nullptr) { ret tmp; } } } return ret; } };Python Codeclass Solution: def sumNumbers(self, root: TreeNode) - int: if not root: return 0 result 0 node_queue, sum_queue [root], [root.val] while node_queue: for i in node_queue: cur_node node_queue.pop(0) cur_val sum_queue.pop(0) if cur_node.left: node_queue.append(cur_node.left) sum_queue.append(cur_val * 10 cur_node.left.val) if cur_node.right: node_queue.append(cur_node.right) sum_queue.append(cur_val * 10 cur_node.right.val) if not (cur_node.left or cur_node.right): result cur_val return result两种写法一一对应递归里 helper 的 cur 参数就是递推里 sum_queue 队头的元素递归里叶子返回 next就是递推里左右孩子均为空时把 tmp 累加到 result。按层处理时每一层结束意味着上一层的全部路径数字都已展开到下一层或已作为叶子求和因此不会出现重复计数或漏加。小结与相关题目本题是二叉树 DFS 递归的经典入门题掌握helper 携带累计值 两个终止条件 左右子树结果相加这一模式后可无障碍迁移到其他路径求和类题目。相关题目sum-of-root-to-leaf-binary-numbers这道题和本题太像了跟一道题没啥区别区别仅在节点值是 0/1 二进制拼接公式从十进制 ×10 换成二进制 ×2。进一步巩固可阅读仓库 thinkings/DFS.md 的深度优先遍历专题与 thinkings/tree.md 的树专题该类中等二叉树题目在 collections/medium.md 中也有收录适合集中刷题对比。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考