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

Учитывая двоичное дерево поиска (BST), найдите наименьшего общего предка (LCA) двух заданных узлов BST.

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

class Solution:

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':    
        if root == None:
            return None

        node = root

        while node:

            if node.val < p.val and node.val < q.val:
                node = node.right

            if node.val > p.val and node.val > q.val:
                node = node.left
            else:
                break

        return node





Войти в полноэкранный режим Выход из полноэкранного режима

Оцените статью
devanswers.ru
Добавить комментарий