Сложность: medium
Дан корень бинарного дерева поиска и узел p в нем. Верните преемника этого узла в порядке возрастания в бинарном дереве поиска (BST). Если у данного узла нет преемника в порядке возрастания в дереве, верните null.
Преемник узла p — это узел с наименьшим ключом, который больше p.val.
Пример:
Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.
👨💻 Алгоритм:
1⃣Определение переменных класса:
Определите две переменные класса: previous и inorderSuccessorNode. Переменная previous будет использоваться при обработке второго случая, а inorderSuccessorNode будет содержать результат, который нужно вернуть.
2⃣Обработка двух случаев:
В функции inorderSuccessor сначала проверьте, какой из двух случаев нужно обработать, проверяя наличие правого дочернего элемента.
Правый дочерний элемент существует:
- присвойте правый дочерний элемент узлу leftmost и итерируйтесь, пока не достигнете узла (leftmost), у которого нет левого дочернего элемента. Итерируйте, присваивая leftmost = leftmost.left, пока не получите левый узел в поддереве.
Правый дочерний элемент не существует:
- определите функцию inorderCase2 и передайте ей узел и узел p.
- выполните простой обход в порядке возрастания: сначала рекурсируйте на левый дочерний элемент узла.
- когда рекурсия вернется, проверьте, равна ли переменная класса previous узлу p. Если это так, значит p является предшественником узла, или, другими словами, узел является преемником узла p. Назначьте inorderSuccessorNode узлу и вернитесь из функции.
- наконец, верните inorderSuccessorNode как результат.
3⃣Итерация и обновление:
В функции inorderCase2 обновляйте previous текущим узлом и продолжайте рекурсировать на правый дочерний элемент.
😎 Решение:
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.previous = None
self.inorderSuccessorNode = None
def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
if p.right:
leftmost = p.right
while leftmost.left:
leftmost = leftmost.left
self.inorderSuccessorNode = leftmost
else:
self.inorderCase2(root, p)
return self.inorderSuccessorNode
def inorderCase2(self, node: TreeNode, p: TreeNode):
if not node:
return
self.inorderCase2(node.left, p)
if self.previous == p and self.inorderSuccessorNode is None:
self.inorderSuccessorNode = node
return
self.previous = node
self.inorderCase2(node.right, p)
Ставь 👍 и забирай 📚 Базу знаний