461. Height-Balanced Check
A botanist records how a climbing vine branches as a binary tree, and root is the base of the vine. She calls the vine even when, at every single junction, the longest chain of branches hanging below its left side and the longest chain hanging below its right side differ in length by at most one. A missing side counts as a chain of length zero.
Return true if the tree rooted at root is even and false otherwise. The rule must hold at every node, not only at the root, and an empty tree is considered even.
Example 1
- Input:
- root = [4,2,9,1,3,null,12]
- Output:
- true
- Explanation:
Every node's two subtrees differ in height by at most one (the right side of 9 is one level taller than its empty left side), so the tree is balanced.
Example 2
- Input:
- root = [7,3,null,2,null,1]
- Output:
- false
- Explanation:
Node 7 has a left subtree of height 3 and no right subtree, a difference of 3, so the tree is not balanced.
Constraints
0 ≤ number of nodes in root ≤ 1000
-1000 ≤ Node.val ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)