LeetCode: наименьший общий предок

Учитывая 2 узла дерева, нам нужен наименьший общий предок. Мы можем легко разделить это на подзадачи. Если оба числа больше корня, тогда мы можем решить проблему для правого поддерева. Если оба числа меньше, мы можем свести проблему к левому поддереву. В противном случае ответ будет корнем. Алгоритм приведен ниже.

1. Если оба значения больше корня, перейдите к правому дочернему элементу
2. если оба значения меньше корня, перейдите к левому дочернему элементу
3. если одно из значений соответствует текущему узлу, вернуть его
4. если одно значение больше, а другое больше текущего узла, вернуть его

Поскольку последние два случая имеют одинаковый результат, мы можем объединить их в разделе else цикла и переместить корень левого или правого дочернего элемента в других случаях.

Примечания:

1. Сложность времени O (log n) для сбалансированного дерева, так как нам нужно пройти от корня к листу. O (n) в худшем случае для левого / правого глубокого дерева
2. Сложность пространства O (1), поскольку дополнительная память не используется

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        while root:
            if p.val < root.val and q.val < root.val:
                root = root.left
            elif p.val > root.val and q.val > root.val:
                root = root.right
            else:
                return root