Lowest Common Ancestor of a Binary Tree
Leetcode #236 | Medium | Деревья | BST
Идея
Заводим указатель, изначально на root, если обе ноды меньше указателя, то идем влево, если обе больше, то спускаемся вправо, иначе - мы нашли и это current. Задача на свойство бинарного дерева поиска
Big-O
- Время
O(H) - Память
O(1)
H - высота дерева
Код
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode cur = root;
while (cur != null) {
if (p.val < cur.val && q.val < cur.val) cur = cur.left;
else if (p.val > cur.val && q.val > cur.val) cur = cur.right;
else return cur;
}
return null;
}
}