When a node's balance factor reaches \pm 2, the repair depends on which way the overweight child leans:
"LL"— left-heavy, and the left child is itself left-heavy or even: one right rotation;"LR"— left-heavy, but the left child is right-heavy: rotate the child left, then the node right;"RR"— right-heavy, and the right child is right-heavy or even: one left rotation;"RL"— right-heavy, but the right child is left-heavy: rotate the child right, then the node left.
Given root, whose balance factor is guaranteed to be 2 or -2, return which case it is. Heights count an empty tree as 0.
Examples
Input: root = build_tree([3, 2, None, 1])
Output: "LL"
Explanation: 3 leans left, and its left child 2 leans left too.
Input: root = build_tree([3, 1, None, None, 2])
Output: "LR"
Explanation: 3 leans left, but its left child 1 leans right.
Constraints
3 <= number of nodes <= 10**4- The root's balance factor is exactly
2or-2.
Goals
- Name the four shapes an unbalanced node can have
- Use the heavy child's own balance to tell a straight line from a zig-zag
- Know which cases need a double rotation