Rewrite Two Complete Trees With Subtree Sums
Two complete binary trees are given in array form: level order with no gaps, where the children of index i are 2i + 1 and 2i + 2. Merge them into one complete tree by adding the values at each index (a node present in only one tree keeps its value), then rewrite every node as the sum of its subtree. Return the resulting array.
subtreeSums([1, 2, 3], [4, 5]) -> [15, 7, 3] // merged [5, 7, 3] subtreeSums([1, 2, 3, 4, 5, 6, 7], []) -> [28, 11, 16, 4, 5, 6, 7] subtreeSums([1, 1, 1, 1], [1, 1]) -> [6, 3, 1, 1]
Hints
Hint 1
The merged array has the length of the longer input; missing entries count as 0.
Hint 2
Walk indices from the end to the start adding each node's value into its parent at (i − 1) / 2, or compute sum[i] = value[i] + sum[2i + 1] + sum[2i + 2] in the same order.