LeetCode 700. 二叉搜索树中的搜索

作者: freesan44 | 来源:发表于2020-07-07 16:24 被阅读0次

题目

给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。

例如,

给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和值: 2
你应该返回如下子树:

      2     
     / \   
    1   3
在上述示例中,如果要找的值是 5,但因为没有节点值为 5,我们应该返回 NULL。

解题思路

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if root == None: return None#特例处理
        # stack = []
        # node = root
        # #先序遍历
        # while node or len(stack)!= 0:
        #     if node:
        #         stack.append(node)
        #         if node.val == val:
        #             return node
        #         node = node.left
        #     else:
        #         node = stack.pop()
        #         node = node.right
        # return None
        #根据搜索树的特性进行遍历
        node = root
        while node:
            if node.val > val:
                node = node.left
            elif node.val < val:
                node = node.right
            else:
                return node
        return None

相关文章

网友评论

    本文标题:LeetCode 700. 二叉搜索树中的搜索

    本文链接:https://www.haomeiwen.com/subject/qqfzqktx.html