题目大意：
从根到叶的二进制数之和
给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
以 10^9 + 7 为模，返回这些数字之和。
示例：
输入：[1,0,1,0,1,0,1] 输出：22 解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
提示：
- 树中的结点数介于
1和1000之间。 - node.val 为
0或1。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1022
解题思路分析：
解法一：
本题可以利用dfs遍历出从顶点到所有叶子节点的路径。理论上，每存在一个叶子节点，就会对应一条路径。由于dfs遍历不会出现重复路径，因此，每一条路径对应的数字相加即是结果。对于任意一个非叶子节点，他都会出现1或者2条分支，当前节点下，所有分支的和应该等于左子节点的和加上右子节点的和（如果某一个子节点为空，则它的和为0）。
看下详细代码：
public int sumRootToLeaf(TreeNode root) {
return dfs(root, 0);
}
// root为当前节点。
// sum为根节点到当前节点父节点之和
// 返回值为当前节点下所有线路的和
int dfs(TreeNode root, int sum){
// 由于节点的值代表2进制的当前位，因此到当前位的和应该为：
// 高位和乘以2再加上当前位。
sum = (sum*2+root.val);
// 如果为叶子节点，直接返回sum。
if(root.left == null && root.right==null){
return sum;
}
int res=0; // 定义返回值。
if(root.left != null){
// 左子节点不为空，递归计算左子节点下所有线路的和
res+=dfs(root.left, sum);
}
if(root.right != null){
// 右子节点不为空，递归计算右子节点下所有线路的和
res+=dfs(root.right, sum);
}
return res;
} 解法二：
解法二实际上与解法一没有本质的区别，不过个人认为更好理解一点。我们定义一个全局变量res，作为返回结果，累加每一条路径的数值。还是利用dfs遍历每一条路径，每到达一个节点，我们计算出根节点到当前节点的和，如果当前节点为叶子节点，那么就将本路径的和加到res中，否则继续向下dfs。
看下代码：
public int sumRootToLeaf(TreeNode root) {
dfs(root, 0);
return res;
}
int res=0; // 返回结果
// root为当前节点。
// sum为根节点到当前节点父节点之和
void dfs(TreeNode root, int sum){
// 由于节点的值代表2进制的当前位，因此到当前位的和应该为：
// 高位和乘以2再加上当前位。
sum = sum * 2 + root.val;
// 如果是叶子节点，将结果加入res
if(root.left==null && root.right==null){
res+=sum;
return;
}
// 向下dfs（递归）左子节点
if(root.left != null){
dfs(root.left, sum);
}
// 向下dfs（递归）右子节点
if(root.right != null){
dfs(root.right, sum);
}
} 本解法用时0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Sum of Root To Leaf Binary Numbers.
Memory Usage: 36.9 MB, less than 100.00% of Java online submissions for Sum of Root To Leaf Binary Numbers.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1022-sum-of-root-to-leaf-binary-numbers-解题思路分析/