Validate a Max Heap
Problem statement
Determine whether a given binary tree is a max heap. Both conditions must hold:
- The tree is complete: every level except possibly the last is full, and the last level is filled from left to right.
- Every parent value is greater than or equal to each existing child value.
The tree is given by three arrays whose entries match by index. Node i stores values[i]; leftChild[i] and rightChild[i] are child node indices, or -1 when that child is absent. A nonempty tree has root node 0. Node indices are labels; they do not have to follow the tree’s level order.
The input always describes one valid connected binary tree. You only need to check whether it meets the heap rules. Treat an empty tree as a valid max heap.
Function
isMaxHeap(values: int[], leftChild: int[], rightChild: int[]) → booleanExamples
Example 1
values = [9,7,8,1,2]leftChild = [1,3,-1,-1,-1]rightChild = [2,4,-1,-1,-1]return = trueThe last level is filled on the left and all parents dominate their children.
Example 2
values = [9,7]leftChild = [-1,-1]rightChild = [1,-1]return = falseThe root has a right child but no left child, so the tree is incomplete despite valid value order.
Example 3
values = [5,7,4]leftChild = [1,-1,-1]rightChild = [2,-1,-1]return = falseThe tree is complete, but child value 7 exceeds root value 5.
Constraints
0 <= values.length <= 5000; all three arrays have equal lengths.- Values are signed 32-bit integers.
- Each child index is
-1or a valid node index. A nonempty input forms a connected binary tree rooted at node zero, with every other node having exactly one parent.