The height of an empty tree is 0 and the height of a node is 1 + \max of its children's heights, so a leaf has height 1. The balance factor of a node is
\mathrm{bal}(v) \;=\; h(v.\mathrm{left}) - h(v.\mathrm{right})
A tree satisfies the AVL condition when every node has a balance factor of -1, 0 or 1.
Given root, return the values of the nodes whose balance factor is outside that range, in pre-order (node, then left subtree, then right subtree).
Examples
Input: root = build_tree([3, 2, None, 1])
Output: [3]
Explanation: node 3 has a left subtree of height 2 and no right subtree, so its balance factor is 2.
Input: root = build_tree([2, 1, 3])
Output: []
Constraints
0 <= number of nodes <= 10**4- Node values are integers and need not be distinct or ordered.
Goals
- Compute the height of every subtree in one post-order pass
- Turn two heights into a balance factor
- Report the nodes that break the AVL condition, in pre-order