Check Whether a Binary Tree Is a Fibonacci Tree in O(h) Time

Problem: Check Whether a Binary Tree Is a Fibonacci Tree (O(h)) Given the root root of a binary tree, define a Fibonacci Tree (Fib Tree) as follows: For every non-null node node: If node is a leaf, it satisfies the property. If node has both a left child L and a right child R, then it must hold that: node.val = L.val + R.val and both subtrees rooted at L and R are Fibonacci Trees. If a node has exactly one child, the tree is not a Fibonacci Tree. Implement a function that determines whether the tree is a Fibonacci Tree, with the constraint: Required time complexity is O(h) where h is the height of the tree (not the number of nodes). Note: The interview emphasized that n refers to the tree height h, so you must avoid traversing the entire tree. Input format (for testing here) The tree is given as a level-order array, where null denotes a missing node. Output format Print true or false. Constraints 0 <= number of nodes <= 2 * 10^5 -10^9 <= node.val <= 10^9 Tree height h can be up to 2 * 10^5 Examples Input: [3,1,2] Output: true Input: [3,1,null] Output: false Input: [5,2,2,1,1,1,1] Output: true Input: [4,1,2] Output: false Input: [] Output: true Example Input [3,1,2] Output true