BST дерево поиска легко Leetcode - PullRequest
Новая
       47

BST дерево поиска легко Leetcode

0 голосов
/ 24 сентября 2019

Учитывая корневой узел бинарного дерева поиска (BST) и значение.Вам нужно найти узел в BST, чтобы значение узла было равно заданному значению.Вернуть поддерево с этим узлом.Если такой узел не существует, вы должны вернуть NULL.

это то, что я получаю для моего кода: 

 class Solution:
     def searchBST(self, root: TreeNode, val: int) -> TreeNode:
         if root == None:
             return None
         elif root.val == val:
             return root
         elif root.val>val:
             root = self.searchBST(root.left,val)
         else:
             root = self.searchBST(root.right,val)

, который, кажется, выводит None.но если заменить строку 

 root = self.searchBST(root.left,val)

на 

 return self.searchBST(root.left,val)

то же самое с root.right

, то это работает.Я не слишком хорош в рекурсии, но как мы можем это сделать 

 return self.searchBST(root.left,val)

Разве searchBST (..) не возвращает TreeNode, так что нам не нужно помещать триод в переменную root?

Ответы [ 2 ]

0 голосов
/ 24 сентября 2019

Вы должны явно указать Python, что вы хотите, чтобы функция возвращала.Это то, что вы делаете со строками return None и return root.

В случаях left и right вы изменяете только локальное значение параметра root, не изменяявсе, что выходит за рамки функции.Нет явного return - это то же самое, что и return None.

Замена двух root = на return действительно должна работать.

0 голосов
/ 24 сентября 2019

Нет, как упоминалось в вопросе, вам нужно вернуть узел, который соответствует val.

Чтобы сделать это, вы должны вернуть адрес узла, если вы найдете значение, и None, если нет.

Порядок обратного распространения значения либо корневого адреса, либо Null (в случае не найден), поэтому вы должны возвращать какой-либо адрес на каждом шаге.

Если у вас возникли проблемы с рекурсией, перейдите ситерационный обход. 

root iterativeSearch(struct Node* root, int key) 
{ 
    // Traverse untill root reaches to dead end 
    while (root != NULL) { 
        // pass right subtree as new tree 
        if (key > root->data) 
            root = root->right; 

        // pass left subtree as new tree 
        else if (key < root->data) 
            root = root->left; 
        else
            return root; // if the key is found return 1 
    } 
    return  Null; 
}

Перейдите к этому для рекурсивных визуализаций: https://www.cs.usfca.edu/~galles/visualization/BST.html

...