Kth самый маленький элемент в оптимизированном BST-решении

Question

Я проходил через эту проблему с кодом leetcode.

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

1. Одно из решений - выполнить обход по порядку.Пройдите через это и найдите kth самый маленькийhttps://www.programcreek.com/2014/07/leetcode-kth-smallest-element-in-a-bst-java/

2. Другое решение, с которым я столкнулся - это где мы передаем int [] {poss, val} и рекурсивно

Однако ни одно из этих действий не решает последующие действия

Что делать, если BST часто изменяется (операции вставки / удаления), и вам нужно часто находить k-е наименьшее?Как бы вы оптимизировали подпрограмму kthSmallest?

У кого-нибудь есть реализация, решающая эту проблему.Я видел неполный пример использования собственного TreeNode со счетчиком, но он не подходит, поскольку TreeNode передается.

Answer 1

Что изменяется при точной реализации отложенного удаления в бинарном дереве поиска? Опция отложенного удаления является опцией.Дело в том, что у вас в основном есть логическое значение флага для каждого узла, указывающее, удален он или нет (но не изменяет структуру вообще.)