Re: Учитывая двоичное дерево поиска и число, найдите путь, данные узла которого добавлены, чтобы быть заданным числом
Я видел эту проблему: учитывая двоичное дерево поиска и число, найдите путь, данные узла которого добавлены к данному числу.,
На нем написано, что При наличии бинарного дерева поиска и числа найдите, существует ли путь от корня к листу, чтобы все числа на пути складывались в заданное число.
Кажется, что все в этой теме знают рекурсивный способ сделать это.
Я что-то пропустил? Как вы решаете это рекурсивно? Вы должны грубой силой целое дерево?
Может ли кто-нибудь дать общее представление (грубая идея) о том, как это сделать?
2 ответа
Рекурсивный подход делается что-то вроде f(node, len) и когда вы проходите через левый или правый узел, вы меняете его на f(node->left, len-left) или же f(node->right,len-right), Когда вы спускаетесь к листу, вы проверяете, len==0 и все сделано.
Этот рекурсивный подход на самом деле такой же, как и грубая сила, однако вы можете использовать технику запоминания, чтобы сделать ее быстрее, как я говорил в этом посте.
Почти так, как вы ожидаете: выполните обход дерева, где вызов дочернего узла имеет целевое значение целевого значения вызывающего абонента за вычетом значения вызывающего абонента; поиск останавливается, когда у листа есть целевое значение. Поскольку это BST, вы сможете отключить поиск нужного потомка, если цель этого потомка меньше значения текущего узла (b/c, все в правом поддереве не меньше).