Ближайший общий предок в бинарном дереве

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

Даны два узла p иq бинарного дерева, вернуть их ближайший общий предокт, lowest common ancestor (LCA).

У каждого узла есть указатель на родителя. Определение Node следуюшее:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

По определению LCA в Wikipedia: "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)."

Пример 1:

Дано: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Результат: 3
Пояснение: 3 - ближайший общий предок и для 5, и для 1

Пример 2:

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

Пример 3:

Дано: root = [1,2], p = 1, q = 2
Результат: 1

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

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

Идея решения

Надо понять, на какой глубине от корня находятся заданные вершины p и q. Заем нужно найти их предков, чтобы они были на одинаковой глубине. Например, если p глубже q, то надо найти предка p, который был бы на одинаковой глубине с q. Возможно, это и будет собственно узел q, тогда общий ближайший предок для обоих узлов будет q,

Иначе, мы будем двигаться от q и предка p параллельно вверх, пока не встремися в общем узле. Это и будет ближайший общий предок.

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

 class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        int ph = findHeight(p);
        int qh = findHeight(q);
        if (ph<qh) {
            return findAnc(p, q, ph, qh);
        } else {
            return findAnc(q, p, qh, ph);
        }
    }
    
    private int findHeight(Node n) {
        int height = 0;
        while(n.parent!=null) {
            n = n.parent;
            height++;
        }
        return height;
    }
    
    private Node findAnc(Node p, Node q, int pheight, int qheight) {
        while(qheight>pheight) {
            q = q.parent;
            //System.out.println("current q = " + q.val);
            qheight--;
        }
        if (p==q) return q;
        while(pheight>0) {
            p=p.parent;
            q=q.parent;
            pheight--;
            if (p==q) return p;
        }
        return p;
    }
}