https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/
X> https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/discuss/270770/JAVA-SOLUTION-BEAT-100
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
We recursively pass the current value of path to the children.
If
If
we double the value from its parent and add the node's value,
like the process of transforming base 2 to base 10.
If
root == null
, no value, return 0.If
root != null
,we double the value from its parent and add the node's value,
like the process of transforming base 2 to base 10.
In the end of recursion,
if
return the current
if
root.left == root.right == null
,return the current
val
.Time Complexity:
O(N)
time, O(logN)
for recursion. int mod = 1000000007;
public int sumRootToLeaf(TreeNode root) {
return dfs(root, 0);
}
public int dfs(TreeNode root, int val) {
if (root == null) return 0;
val = (val * 2 + root.val) % mod;
return (root.left == root.right ? val : dfs(root.left, val) + dfs(root.right, val)) % mod;
}
X> https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/discuss/270770/JAVA-SOLUTION-BEAT-100
public int sumRootToLeaf(TreeNode root) {
List<String> list = new ArrayList<>();
helper(list, root, new StringBuilder().append(Integer.toString(root.val)));
int res = 0;
for (String ele: list) {
res += Integer.parseInt(ele, 2);
}
return res;
}
private void helper(List<String> list, TreeNode root, StringBuilder sb) {
if (root == null) return;
if (root.left == null && root.right == null) {
list.add(sb.toString());
return;
}
if (root.left != null) {
sb.append(Integer.toString(root.left.val));
helper(list, root.left, sb);
sb.deleteCharAt(sb.length() - 1);
}
if (root.right != null) {
sb.append(Integer.toString(root.right.val));
helper(list, root.right, sb);
sb.deleteCharAt(sb.length() - 1);
}
}