Наименьший общий предок в бинарном поисковом дереве

Источник: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree

Дано бинарное дерево поиска (BST), найдите вершин наименьшего общего предка (LCA), если даные 2 вершины из этого BST.   

Согласно определению LCA в Википедии: «Наименьший общий предок определяется между двумя узлами p и q как наиближайшая к ним вершина в T, которая имеет как p, так и q в качестве потомков (где мы позволяем вершине быть потомком самого себя). ”

Пример 1:

Дано: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Результат: 6
Explanation: LCA вершин 2 и 8 - это 6.

Пример 2: то же дерево, что и выше

Дано: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Результат: 2
Explanation: LCA вершин 2 и 4 - это 2, поскольку вершина может быть потомком самой себя, согласно определнию.

Example 3:

Дано: root = [2,1], p = 2, q = 1
Output: 2

Ограничения:

• Число вершин в дереве находится в диапазоне [2, 105].
• -109 <= Node.val <= 109
• Все Node.val уникальны.
• p != q
• p и q существуют (не null).
  

Идея решения

Корень - это всегда общий предок любых других вершин в BST. Он будет LCA, если одна заданная вершина относительно корня находится в левом подереве (либо является корнем), а вторая - в правом (либо является корнем). Нам нужно минимизировать этот результат, если ни одна из вершин не является корнем.

Для этого нам нужно рассмотреть левое и правое поддерево корня. 

1. Если корень поддерева и есть одна из искомых вершин, то мы возвращаем этот корень поддерева. 
2. (рекурсивный переход) Если корень поддерева не является искомой вершиной, то рекурсивно рассматриваем его правое и левое поддерево.
3. (сборка рекурсии) Если результаты левого и правого поддерева равны null, поддерево не содержит ни одной из заданой вершины, то есть поддерево с текущем корнем не может быть общим предком, и мы возвращаем null.
   
4. Иначе рассматриваем вариации:
1. если оба результата (левый и правый) не равны null, то искомые вершины находятся в разных поддеревьях - значит корень данного поддерева является общим предком.
2. иначе возвращаем ненулевой результат.
   

Рассмотрим, например, вершины 3 и 5.

lca(3) =3, lca(5)=5, 

lca(4)=4, поскольку 4.left=3, 4.right=5 и оба результата не нулевые.

Далее lca(0)=null. Значит lca(2) = nonNull(lca(0), lca(4)) = 4.

lca(8)=null. Значит lca(6) = nonNull(lca(2), lca(6)) = 4

Имплементация 

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

class Solution {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (root == null) return null; // проверка пограничного случая, анализировать нечего

if (root == p || root == q) return root; // шаг 1

 

        // шаг 2 рекурсивный переход 

TreeNode left = lowestCommonAncestor(root.left, p, q);

TreeNode right = lowestCommonAncestor(root.right, p, q);

 

        // случай в шаге 4.2

if (left!=null && right == null) {

return left;

}

if (left==null && right!=null) {

return right;

}

 

        // случай в шаге 4.1 

if (left!=null && right!=null) {

return root;

}

return null; // шаг 3

}

}

В снти существует более элегантное решение, которое тоже сводится к рассмотренным случаям:

class Solution {
    public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lca(root.left, p, q);
        TreeNode right = lca(root.right, p, q);
        return left == null ? right : right == null ? left : root;
    }
}