1022. 从根到叶的二进制数之和

大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

二叉树从根节点到叶子节点，是一条路径；把路径上的值，构成一个二进制数。

求根节点到叶子节点所有路径的构成数字之和。

解题方法

分析

本题让我们求「所有」路径之和，一个很简单的想法就是：使用一个变量，保存「已经访问过的所有」路径之和。

这样，当我们把所有路径都访问一遍以后，就能得到题目想要的结果。

我定义了全局的变量 res = 0，当每次遇到叶子节点的时候，就把整条路径的数字之和，累加到 res中。

由于在遍历过程到每个节点时的「路径和」都是不一样的，因此还需要一个变量 preSum表示在遇到当前节点前的所有路径之和。

上述就是本题的思考过程。

递归

遇到二叉树的题目，一般都是 DFS 或者 BFS 解决。其中用到 DFS（递归） 场景更多。

在上面的分析中，我们发现可以把大问题划分成小问题：想要求「根节点」到「叶子节点」的路径构成的数字是多少，需要先求「根节点的子节点」到「叶子节点」的路径构成的数字是多少……

这就形成了递归。

递归函数的定义：到达节点 的路径已经构成数字是 $preSum$； 求以当前开始，访问到每个叶子节点路径构成的 $preSum$。

递归函数产生的副作用：当到达叶子节点时，把 累加到全局变量 中。

代码

代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sumRootToLeaf(self, root):
        self.res = 0
        self.dfs(root, 0)
        return self.res
    def dfs(self, root, preSum):
        if not root: return
        preSum = preSum * 2 + root.val
        if not root.left and not root.right:
            self.res += preSum
        self.dfs(root.left, preSum)
        self.dfs(root.right, preSum)

复杂度

• 时间复杂度：，是二叉树节点个数。
• 空间复杂度：，递归使用的栈空间。

  总结

1. 二叉树，第一反映就是递归。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会
• 我写的 1000 道 LeetCode 题解，都在这里了，免费拿走。