Family Distance
Medium · tree dfs
A family tree is stored as a binary tree: every person is a node, and each node's children are its left and right nodes. All values in the tree are distinct, so a value identifies one person.
You are given the root of the tree and two values a and b. Both of them are in the tree. The distance between two people is the smallest number of parent-child links you must follow to get from one to the other. You may walk up to a parent as well as down to a child.
Return the distance between the person with value a and the person with value b. If a and b are the same value, the distance is 0.
Examples
Example 1
Input: root = [10, 4, 15, 2, 7, 12, 20, null, null, 6, 9], a = 6, b = 12
Output: 5
Go 6 -> 7 -> 4 -> 10 -> 15 -> 12. That is five links.
Example 2
Input: root = [10, 4, 15, 2, 7, 12, 20, null, null, 6, 9], a = 7, b = 9
Output: 1
9 is a child of 7, so they are one link apart.
Example 3
Input: root = [10, 4, 15, 2, 7, 12, 20, null, null, 6, 9], a = 4, b = 4
Output: 0
It is the same person.
Constraints
- The number of nodes is in the range [1, 500].
- -1000 <= Node.val <= 1000
- All node values are distinct.
- a and b are both values that appear in the tree.