0700-二叉搜索树中的搜索

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

例如,

给定二叉搜索树:
0700-二叉搜索树中的搜索

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

0700-二叉搜索树中的搜索

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/search-in-a-binary-search-tree

参考:

python

# 0700.二叉搜索树中搜索
class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        """
        递归法
        :param root:
        :param val:
        :return:
        """
        if not root or root.val == val:
            return root

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

        return None

class Solution2:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        """
        迭代法
        :param root:
        :param val:
        :return:
        """
        while root:
            if root.val > val:
                root = root.left
            elif root.val < val:
                root = root.right
            else:
                return root
        return None

golang

package binaryTree

// 递归
func searchBST(root *TreeNode, val int) *TreeNode {
	if root == nil || root.Val == val {
		return root
	}
	if root.Val > val {
		return searchBST(root.Left, val)
	}

	return searchBST(root.Right, val)
}

// 迭代
func searchBST1(root *TreeNode, val int) *TreeNode {
	for root != nil {
		if root.Val > val {
			root = root.Left
		} else if root.Val < val {
			root = root.Right
		} else {
			break
		}
	}
	return root
}

上一篇:数据库学习总结


下一篇:手把手教你学Dapr - 1. .Net开发者的大时代