BST树搜索简单leetcode

Question

给定二叉搜索树 (BST) 的根节点和一个值。需要在 BST 中找到该节点的值等于给定值的节点。 Return 以该节点为根的子树。如果这样的节点不存在，你应该 return 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(..) return TreeNode 所以我们不必将树节点放在变量 root 中吗？

Answer 1

不，如问题所述，您需要 return 与 val 匹配的节点。

为此，如果找到该值，则必须 return 节点地址，否则 None。

为了向后传播根地址或 Null（如果未找到）的值，因此您必须 return 在每一步都使用一些地址。

如果递归有问题，请使用迭代遍历。

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

Answer 2

您必须明确地告诉 Python 您希望函数 return 做什么。这就是您对 return None 和 return root 行所做的。

在 left 和 right 情况下，您只是更改参数 root 的局部值，而不更改函数范围之外的任何内容。没有明确的 return 与 return None 相同。

将两个 root = 替换为 return 确实应该可以完成工作。

Answer 3

class Solution(object):
def is_leaf(self,root):
        return root.left is None and root.right is None

def searchBST(self, root, val):

    if root is None:
        return root
    if self.is_leaf(root):
        if root.val == val:
            return root
        return None

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

BST树搜索简单leetcode

BST tree search easy leetcode

python

binary-tree

binary-search-tree