Sum of Binary Tree Boundary Nodes
Snowflake● MediumFULLTIMEPHONE SCREENProblem statement
You are given a binary tree as three arrays values, left, and right. Node i has value values[i] and children left[i] and right[i]; -1 means that child is absent. The root is node 0. An empty array represents an empty tree.
Return the sum of the values of every distinct boundary node. The boundary contains:
- The root.
- The left boundary: start at the root's left child and repeatedly choose the left child when present, otherwise the right child. Include only non-leaf nodes along this path.
- Every leaf in the tree. A leaf has neither child.
- The right boundary: start at the root's right child and repeatedly choose the right child when present, otherwise the left child. Include only non-leaf nodes along this path.
Count each node once, even when it belongs to more than one category. Equal values on different nodes are counted separately. Return 0 for an empty tree. Use signed 64-bit arithmetic.
Function
boundarySum(values: int[], left: int[], right: int[]) → longExamples
Example 1
values = [1,2,3,4,5,6,7]left = [1,3,5,-1,-1,-1,-1]right = [2,4,6,-1,-1,-1,-1]return = 28Every node in this tree is on its boundary, so the sum is 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.
Example 2
values = [10,20,30,40,50,60,70,80]left = [1,3,-1,-1,7,-1,-1,-1]right = [2,4,5,-1,6,-1,-1,-1]return = 310The boundary is nodes 0, 1, 2, 3, 5, 6, 7. Node 4 is an interior non-leaf, so its value 50 is excluded.
Example 3
values = [9]left = [-1]right = [-1]return = 9The root is also a leaf, but it contributes only once.
Constraints
0 <= values.length <= 100000.left.length == right.length == values.length.-10^9 <= values[i] <= 10^9.- Every child is
-1or a valid node index. - The arrays describe one valid binary tree rooted at node
0when nonempty: every other node has one parent, and all nodes are reachable.