Сложность: 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 Solution {
private TreeNode previous;
private TreeNode inorderSuccessorNode;
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if (p.right != null) {
TreeNode leftmost = p.right;
while (leftmost.left != null) {
leftmost = leftmost.left;
}
this.inorderSuccessorNode = leftmost;
} else {
this.inorderCase2(root, p);
}
return this.inorderSuccessorNode;
}
private void inorderCase2(TreeNode node, TreeNode p) {
if (node == null) {
return;
}
this.inorderCase2(node.left, p);
if (this.previous == p && this.inorderSuccessorNode == null) {
this.inorderSuccessorNode = node;
return;
}
this.previous = node;
this.inorderCase2(node.right, p);
}
}Ставь 👍 и забирай 📚 Базу знаний