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

🔗题目链接：129.求根节点到叶节点数字之和

LeetCode 中等题——这道题是二叉树遍历的经典应用，核心考察「路径追踪」和「数值累加」，两种主流解法（迭代栈、递归）都很直观，适合巩固二叉树的遍历逻辑，今天就来详细拆解每一步思路，帮大家吃透这道题

🧠第一种：解题思路

🚀采用 深度优先搜索 (DFS) 的递归方法：

定义递归函数 sumNumbersHelper(TreeNode root, int sum)，其中 sum 表示从根节点走到当前节点（不包括当前节点）时已经形成的数字。
当走到当前节点时，更新路径值为 num = sum * 10 + root.val。
如果当前节点是叶子节点（即左右子节点均为空），直接返回 num。
否则，继续递归处理左子树和右子树，并将结果相加返回。

📎 复杂度分析

时间复杂度：O(n)，其中 n 是二叉树节点数。每个节点访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归栈的深度取决于树的高度（最坏情况为 O(n)）。

途中遇到的一些纠结点：

1. 需借助其辅助函数：
- 这属于“向下传递”类型，但原函数参数只有TreeNode，无法进行递归调用，声明辅助函数，向下传入累加和num，因此们可以总结出一点如下:
1. 递归函数返回什么要想清楚？以 root 为起点的左右路径的数字之和。这才是正确的递归思路

🎯代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        return sumNumbersHelper(root, 0);
    }

    public int sumNumbersHelper(TreeNode root, int sum) {
        if (root == null) return 0;

        // 1. 算出走到当前节点时的路径值
        int num = sum * 10 + root.val;

        // 2. 如果是叶子节点，直接返回刚才算出的路径值
        if (root.left == null && root.right == null) {
            return num;
        }

        // 3. 如果不是叶子节点，递归往下走，把左右两边的结果加起来返回
        return sumNumbersHelper(root.left, num) + sumNumbersHelper(root.right, num);
    }
}