二叉树深度优先搜索技巧：计算布尔值与路径数字之和

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

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

题目内容

给你一个二叉树的根节点 root，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字：例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123。 计算从根节点到叶节点生成的所有数字之和。

叶节点是指没有子节点的节点。

示例 1： 输入：root = [1,2,3] 输出：25 解释：从根到叶子节点路径 1->2 代表数字 12，从根到叶子节点路径 1->3 代表数字 13。因此，数字总和 = 12 + 13 = 25

示例 2： 输入：root = [4,9,0,5,1] 输出：1026 解释：从根到叶子节点路径 4->9->5 代表数字 495，从根到叶子节点路径 4->9->1 代表数字 491，从根到叶子节点路径 4->0 代表数字 40。因此，数字总和 = 495 + 491 + 40 = 1026

提示：

• 树中节点的数目在范围 [1, 1000] 内
• 0 <= Node.val <= 9
• 树的深度不超过 10

分析题意

以上图得 1 节点为例：

1. 需要接收来自上一层的 49。
2. 需要往下传递 49*10+1=491。
3. 到达叶子节点，需要将结果返回。 分析出这三点，就不难写出递归代码了。

具体步骤

1. 大量重复子问题 (函数头): 上一层节点×10+根节点传给子节点。直到叶子节点才返回最终结果。int dfs(root, presum)。presum 记录上一层的值。
2. 某一子问题的工作流程:
   • 计算当前的值，presum*10+root.val;
   • 前序遍历递归左子树
   • 前序遍历递归右子树
3. 递归出口: 当前节点为叶子节点时，返回结果。

代码实现

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

    public int dfs(TreeNode root, int presum) {
        presum = presum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return presum;
        }
        int ret = 0;
        if (root.left != null) {
            ret += dfs(root.left, presum);
        }
        if (root.right != null) {
            ret += dfs(root.right, presum);
        }
        return ret;
    }
}

总结

凡是能用递归来解决的二叉树题目，要么是前序遍历，要么是后序遍历，还有一部分是中序遍历。大部分题都是这样的，一般可以先尝试前序，再后序，最后中序。