Re: Учитывая двоичное дерево поиска и число, найдите путь, данные узла которого добавлены, чтобы быть заданным числом

Question

Я видел эту проблему: Учитывая двоичное дерево поиска и число, найдите путь, данные узла которого добавлены к данному числу. .

На нем написано, что с учетом бинарного дерева поиска и числа найдите, существует ли путь от корня к листу так, чтобы все числа на пути складывались в заданное число.

Кажется, что все в этой теме знают рекурсивный способ сделать это.

Я что-то упустил? Как вы решаете это рекурсивно? Вы должны грубой силой целое дерево?

Может ли кто-нибудь дать общее представление (грубая идея) о том, как это сделать?

Answer 1

Рекурсивный подход выполняется примерно как f(node, len), и когда вы проходите через левый или правый узел, вы меняете его на f(node->left, len-left) или f(node->right,len-right).Когда вы спускаетесь к листу, вы проверяете, выполняется ли текущий len==0 и все.

Этот рекурсивный подход фактически такой же, как грубая сила, однако вы можете использовать технику запоминания, чтобы сделать ее быстрее,так же, как я сказал в этом посте.

Answer 2

Почти так, как вы ожидаете: выполните обход дерева, где вызов дочернего узла имеет целевое значение целевого значения вызывающего абонента за вычетом значения вызывающего абонента;поиск останавливается, когда у листа есть целевое значение.Поскольку это BST, вы сможете отключить поиск нужного потомка, если цель этого потомка меньше значения текущего узла (b / c, все в правом поддереве не меньше).