roma-dxunvrs
23 lines
974 B
Markdown
23 lines
974 B
Markdown
Leetcode #1650 | #Medium | [[Деревья]] | [[BST]] | [[Математика]]
|
|
## Идея
|
|
Отличие от [[Lowest Common Ancestor of a Binary Tree]] - нам не дают корень.
|
|
В чем логика. Пусть путь от p до общего предка - A, от q - B, часть от предка до null (выход за корень) - C. Когда указатель от p доходит до null мы скидываем его в q, для q делаем такое же, только скидываем до p. А теперь посчитаем пути.
|
|
a - A + C + B
|
|
b - B + C + A
|
|
Вот и все
|
|
## Big-O
|
|
- Время ```O(N)```
|
|
- Память ```O(1)```
|
|
## Код
|
|
```Java
|
|
class Solution {
|
|
public Node lowestCommonAncestor(Node p, Node q) {
|
|
Node a = p, b = q;
|
|
while (a != b) {
|
|
a = (a == null) ? q : a.parent;
|
|
b = (b == null) ? p : b.parent;
|
|
}
|
|
return a;
|
|
}
|
|
}
|
|
``` |