LeetCode 700: 二叉搜索树中的搜索 Search in a Binary Search Tree

爱写bug

发布于 2020-03-25 17:53:27

4720

发布于 2020-03-25 17:53:27

文章被收录于专栏：爱写Bug

题目:

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

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.

例如，

给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和值: 2

你应该返回如下子树:

      2     
     / \   
    1   3

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

解题思路:

二叉搜索树中的搜索操作, 可根据 BST 的特性，对于每个节点：

如果目标值等于节点的值，则返回节点;
如果目标值小于节点的值，则继续在左子树中搜索;
如果目标值大于节点的值，则继续在右子树中搜索。

递归法:

Java:

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null)
            return null;
        if (val == root.val)
            return root;
        if (val > root.val)
            return searchBST(root.right, val);
        else
            return searchBST(root.left, val);
    }
}

Python:

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

Golang:

func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val == val {
        return root
    }
    if val > root.Val {
        return searchBST(root.Right, val)
    } else {
        return searchBST(root.Left, val)
    }
}

迭代法:

Java:

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root!=null){
            if (root.val == val)
                return root;
            if (val > root.val)
                root=root.right;
            else
                root=root.left;
        }
        return null;
    }
}

Python:

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

Golang:

func searchBST(root *TreeNode, val int) *TreeNode {
    for root != nil {
        if root.Val == val {
            return root
        }
        if val > root.Val {
            root = root.Right
        } else {
            root = root.Left
        }
    }
    return nil
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-03-16，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js