Поиск в бинарном дереве поиска

Question

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

Например,

Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2
You should return this subtree:

  2     
 / \   
1   3

В приведенном выше примере, если мы хотим найти значение 5, так как узла нет со значением 5 мы должны вернуть NULL.

Обратите внимание, что пустое дерево представлено как NULL, поэтому вы увидите ожидаемый результат (сериализованный формат дерева) как [], а не ноль.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:


        if(root is None) or (root.val == val):
            return root

        if(root.val>val):
            return self.searchBST(root.right,val)
        elif(root.val<val):
            return self.searchBST(root.left,val)

Это код, который я написал,

Теперь, если я изменю второе условие if на:

return self.searchBST(root.left, val) if val < root.val \
            else self.searchBST(root.right, val)

Код работает хорошо, ПОМОГИТЕ?

Answer 1

Ваш код не совсем правильный, если текущее значение узла (root) больше, чем искомое значение, тогда go влево, в противном случае go вправо.

В вашем текущий код, вы делаете противоположное.

Итак, правильный путь будет выглядеть так:

if(root.val>val):
        return self.searchBST(root.left,val) #changed to root.left
    elif(root.val<val):
        return self.searchBST(root.right,val) #changed to root.right

Answer 2

Вы перевернули значения. Если root.val > val, вам нужно искать root.left.

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:


        if(root is None) or (root.val == val):
            return root

        if(root.val>val):
            return self.searchBST(root.left,val) // FLIPPED
        elif(root.val<val):
            return self.searchBST(root.right,val) // FLIPPED