原文链接 [每日 LeetCode] 1022. Sum of Root To Leaf Binary Numbers
Description:
Given a binary tree, each node has value 0
or 1
. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0 -> 1 -> 1 -> 0 -> 1
, then this could represent 01101
in binary, which is 13
.
For all leaves in the tree, consider the numbers represented by the path from the root to that leaf.
Return the sum of these numbers.
Example 1:
Input: [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
Note:
- The number of nodes in the tree is between
1
and1000
. - node.val is
0
or1
. - The answer will not exceed
2^31 - 1
.
思路:本题要求二叉树中所有路径的二进制编码之和,涉及到二叉树的遍历。在此使用 DFS,遍历每层时记录下当前的数值之和,直到叶子节点。注意初始化二叉树的方式,默认初始化为完全二叉树。
C++ 代码
/**
* 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:
int sumRootToLeaf(TreeNode* root) {
if (!root)
return 0;
int sum = 0;
DFS(root, 0, sum);
return sum;
}
void DFS(TreeNode *root, int cur_sum, int& sum){
if (!root)
return;
cur_sum = 2 * cur_sum + root->val;
if (!root->left && !root->right)
sum += cur_sum;
if (root->left)
DFS(root->left, cur_sum, sum);
if (root->right)
DFS(root->right, cur_sum, sum);
}
};
运行时间:8ms
运行内存:17.2M
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于