本文主要是介绍1022. Sum of Root To Leaf Binary Numbers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1022. 从根到叶的二进制数之和
给出一棵二叉树，其上每个结点的值都是
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。
解法一
//时间复杂度O(n), 空间复杂度O(logn)
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:void sumRootToLeaf(TreeNode* root, int cur, int& sum) {if(!root) return;if(!root->left && !root->right) sum += (cur %= 1000000007) * 2 + root->val;sumRootToLeaf(root->left, (cur %= 1000000007) * 2 + root->val, sum);sumRootToLeaf(root->right, (cur %= 1000000007) * 2 + root->val, sum);}int sumRootToLeaf(TreeNode* root) {int sum = 0;sumRootToLeaf(root, 0, sum);return sum;}
};思路：
DFS遍历。当前二进制前缀构成的数字对1000000007取余记为cur，另一变量sum记录所求的和。
对于递归遍历的每一层，都先令cur %= 1000000007，再乘以2（左移1位），加上root->val（低位），所得的结果传入下一层。这一步骤与1018类似。
2019/09/05 22:51
这篇关于1022. Sum of Root To Leaf Binary Numbers的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
