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:

1. The number of nodes in the tree is between 1 and 1000.
2. node.val is 0 or 1.
3. The answer will not exceed 2^31 - 1.

从根到叶的二进制数之和。题意是给一个二叉树，请你返回每条从根节点到叶子节点的路径和。由于路径上的点只有0或1，所以需要把结果再convert成十进制。

这道题的题目跟129题几乎一样，思路也是几乎一样，唯一不同的地方是这道题需要处理二进制到十进制的问题。之前的十进制，每次进位的时候是乘以10，这道题乘以2即可。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     int res = 0;
 3     
 4     public int sumRootToLeaf(TreeNode root) {
 5         helper(root, 0);
 6         return res;
 7     }
 8     
 9     private void helper(TreeNode root, int sum) {
10         if (root == null) {
11             return;
12         }
13         sum = sum * 2 + root.val;
14         if (root.left == null && root.right == null) {
15             res += sum;
16         }
17         helper(root.left, sum);
18         helper(root.right, sum);
19     }
20 }

 

相关题目

129. Sum Root to Leaf Numbers

1022. Sum of Root To Leaf Binary Numbers

LeetCode 题目总结