639，二叉搜索树中的搜索
问题描述
来源：LeetCode第700题
难度：简单
给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。
示例 1:
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]
示例 2:
输入：root = [4,2,7,1,3], val = 5
输出：[]
提示：
数中节点数在[1, 5000]范围内
1 <= Node.val <= 10^7
root 是二叉搜索树
1 <= val <= 10^7
问题分析
这是新年写的第一道题解，好久没写了，突然感觉有点生疏，就先拿一道简单的练练手，找找感觉。希望新的一年能学勤快一些，不要在偷懒了，好了，言归正传，我们来看一下这题的答案。
这题说的是在二叉搜索树中的查找，我们首先要搞懂什么是二叉搜索树。维基百科上对二叉搜索树是这样描述的：
二叉查找树（英语：Binary Search Tree），也称为二叉查找树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。
一句话概括就是二叉搜索树每个节点的值都比他的所有左子节点值大，并且比他的所有右子节点值小。所以这题查找的时候从根节点开始，如果找到就返回，如果比根节点小就往左子节点查找，否则就往右子节点查找……
public TreeNode searchBST(TreeNode root, int val) {
//如果节点为空就返回空，或者找到了要找的节点也直接返回
if (root == null || root.val == val)
return root;
//如果val比当前节点的值小就在当前节点的左子节点来找，
//否则就在当前节点的右子节点来找
if (val < root.val)
return searchBST(root.left, val);
else
return searchBST(root.right, val);
}
代码比较简单，我们还可以改为非递归的方式
public TreeNode searchBST(TreeNode root, int val) {
//如果当前节点不为空，并且也不是我们要找的,就继续查找
while (root != null && root.val != val)
root = val < root.val ? root.left : root.right;
return root;
}
截止到目前我已经写了600多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有1000多页，大家可以在下面公众号“数据结构和算法”中回复关键字“pdf”即可获取下载链接。
想学习算法，还可以长按下面二维码加我微信，我给你拉到算法学习群，在工作中或者学习中遇到不会的问题都可以在群里讨论。