0129. Sum Root to Leaf Numbers ============================== 题目信息 -------- :题号: 0129. 求根节点到叶节点数字之和 :难度: Medium :主题: 二叉树、深度优先搜索、路径状态、十进制前缀 :原题: `LeetCode 0129 `_ :重点: 将完整路径压缩为十进制前缀,只在真正叶节点结算,并理解递归参数与显式栈元素的对应关系 题目重述 -------- 给定一棵二叉树,每个节点保存 ``0..9`` 的一个数字。每条从根节点到叶节点的路径,按访问顺序组成一个 十进制整数;返回所有这些整数之和。只有左右孩子都为空的节点才是叶节点,路径中的前导零按普通整数规则 处理。题目保证最终答案可用 32 位有符号整数表示。 自建示例 -------- * ``root = [3, 1, 7, 0, 4]``:三条路径表示 ``310``、``314``、``37``,返回 ``661``; * ``root = [0, null, 6, null, 2]``:唯一数字是 ``062``,数值为 ``62``; * ``root = [5, 2, null, 9]``:节点 ``2`` 仍有左孩子,不是叶子;唯一完整路径为 ``5 -> 2 -> 9``, 返回 ``529``。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: void collectCompletePath( TreeNode* node, std::vector& digits, long long& total ) { if (node == nullptr) { return; } digits.push_back(node->val); if (node->left == nullptr && node->right == nullptr) { long long number = 0; for (int digit : digits) { number = number * 10 + digit; } total += number; } else { collectCompletePath(node->left, digits, total); collectCompletePath(node->right, digits, total); } digits.pop_back(); } long long sumWithPrefix(TreeNode* node, long long parentPrefix) { if (node == nullptr) { return 0; } const long long current = parentPrefix * 10 + node->val; if (node->left == nullptr && node->right == nullptr) { return current; } return sumWithPrefix(node->left, current) + sumWithPrefix(node->right, current); } long long sumWithExplicitStack(TreeNode* root) { if (root == nullptr) { return 0; } std::stack> pending; pending.push({root, 0}); long long total = 0; while (!pending.empty()) { auto [node, parentPrefix] = pending.top(); pending.pop(); const long long current = parentPrefix * 10 + node->val; if (node->left == nullptr && node->right == nullptr) { total += current; continue; } if (node->right != nullptr) { pending.push({node->right, current}); } if (node->left != nullptr) { pending.push({node->left, current}); } } return total; } public: int sumNumbers(TreeNode* root) { return static_cast(sumWithPrefix(root, 0)); } }; 题解 ---- 原始做法:先保存路径,再在叶子解释它 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 从根到叶的选择空间天然是一棵树:到达节点后,下一步可能进入左孩子或右孩子。最直接的 DFS 用 ``digits`` 保存当前路径;进入节点时追加一位,退出时弹出一位。到达叶子后再从头扫描整个数组,按十进制 规则还原数字并加入总和。 ``collectCompletePath`` 的回溯状态是正确的:递归进入某节点时,``digits`` 恰好包含根到该节点的路径; 返回父节点前弹出当前位,左右分支不会互相污染。可是多个叶子共享长前缀时,每个叶子都会再次遍历相同的 前缀。保存每一位也超过了后续计算真正需要的信息。 结构信息:追加一位只依赖已有数值 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 若父路径已经表示整数 ``prefix``,在末尾追加当前数字 ``digit`` 的结果固定为: .. code-block:: text current = prefix * 10 + digit 后续无论再追加哪一位,都只需要 ``current``,不需要知道此前各位分别是什么。于是完整路径数组可以压缩为 一个十进制前缀:递归参数携带父节点之前的值,进入当前节点时更新一次,再把同一个 ``current`` 分别交给 左右子树。 这个状态也自然处理前导零。例如 ``0 -> 6 -> 2`` 依次得到 ``0``、``6``、``62``,无需构造字符串、删除 零或单独解析。 叶节点是唯一结算点 ~~~~~~~~~~~~~~~~~~ 路径必须从根结束于叶子。只有 ``left == nullptr && right == nullptr`` 同时成立,``current`` 才代表一条 完整答案。只判断“至少一个孩子为空”会把单孩子树中的内部节点提前结算;例如 ``5 -> 2 -> 9`` 中节点 ``2`` 的右孩子为空,但 ``52`` 并不是合法根到叶数字。 空指针分支返回零,表示这侧没有叶子、对总和没有贡献。非叶节点的所有完整路径要么进入左子树,要么进入 右子树,两组叶子互不重叠,因此两次递归的返回值可直接相加。 具体走读 ~~~~~~~~ 对 ``[3, 1, 7, 0, 4]``,递归状态按路径演进如下: .. list-table:: :header-rows: 1 * - 当前节点 - 父前缀 - 更新后 ``current`` - 动作 * - ``3`` - ``0`` - ``3`` - 非叶,传给两个孩子 * - ``1`` - ``3`` - ``31`` - 非叶,继续进入 ``0`` 与 ``4`` * - ``0`` - ``31`` - ``310`` - 叶子,返回 ``310`` * - ``4`` - ``31`` - ``314`` - 叶子,返回 ``314`` * - ``7`` - ``3`` - ``37`` - 叶子,返回 ``37`` 节点 ``1`` 返回 ``310 + 314``,根节点再加右侧 ``37``。前缀 ``31`` 只计算一次并传给两个分支,没有在 两个叶子处重新扫描 ``3, 1``。 递归与显式栈的状态对应 ~~~~~~~~~~~~~~~~~~~~~~ ``sumWithPrefix`` 的一次函数调用隐含保存 ``(node, parentPrefix)``。``sumWithExplicitStack`` 把这对状态 直接放进 ``pending``,弹出后执行完全相同的前缀更新和叶子判断。先压右孩子再压左孩子只是让左侧先处理, 不影响加法结果;树中节点有唯一父路径,也不需要访问集合。 显式栈不是更优的渐进算法,而是在树很深、希望避免递归调用栈时的实现替代。主解选择递归前缀,因为状态 转移和子树返回值的含义最直接;路径数组法保留为演进起点,显式栈则展示递归帧究竟保存了什么。 正确性与复杂度 ~~~~~~~~~~~~~~ 每个叶节点在树中只有一条根路径。DFS 恰好访问该叶子一次,并通过逐位递推得到这条路径的十进制值,所以 每个合法数字加入一次;内部节点从不结算,因此没有额外数字。每个节点只做常数工作,主解时间 ``O(n)``、 递归空间 ``O(h)``,其中 ``h`` 为树高。显式栈最坏占 ``O(n)``;完整路径基线还会在每个叶子重新扫描路径, 最坏时间可达 ``O(nh)``。代码使用 ``long long`` 保存中间前缀与部分和,再按题目保证转换为 ``int``。