11##题目地址
22https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
33
4- ## 思路
4+ > 二叉搜索树登场！
55
6- ### 递归法
6+ #700.二叉搜索树中的搜索
77
8- 先来看递归的实现方式 。
8+ 给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL 。
99
10- 依然从递归三要素开始分析：
10+ 例如，
1111
12- * 确定递归函数的参数和返回值
13- * 确定终止条件
14- * 确定单层递归的逻辑
12+ <img src =' ../pics/700.二叉搜索树中的搜索.png ' width =600 > </img ></div >
13+
14+ 在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
15+
16+ #思路
17+
18+ 之前我们讲了都是普通二叉树，那么接下来看看二叉搜索树。
19+
20+ 在[ 关于二叉树，你该了解这些！] ( https://mp.weixin.qq.com/s/_ymfWYvTNd2GvWvC5HOE4A ) 中，我们已经讲过了二叉搜索树。
21+
22+ 二叉搜索树是一个有序树：
23+
24+ * 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
25+ * 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
26+ * 它的左、右子树也分别为二叉搜索树
27+
28+ 这就决定了，二叉搜索树，递归遍历和迭代遍历和普通二叉树都不一样。
29+
30+ 本题，其实就是在二叉搜索树中搜索一个节点。那么我们来看看应该如何遍历。
31+
32+ ##递归法
1533
16341 . 确定递归函数的参数和返回值
1735
@@ -33,17 +51,25 @@ if (root == NULL || root->val == val) return root;
3351
34523 . 确定单层递归的逻辑
3553
36- 来看一下二叉搜索树的单层递归逻辑有何不同， 因为二叉搜索树的节点是有序的，所以可以有方向的去搜索，如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。
54+ 看看二叉搜索树的单层递归逻辑有何不同。
55+
56+ 因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。
57+
58+ 如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。
3759
3860代码如下：
3961
4062```
41- if (root->val > val) return searchBST(root->left, val);
63+ if (root->val > val) return searchBST(root->left, val); // 注意这里加了return
4264if (root->val < val) return searchBST(root->right, val);
4365return NULL;
4466```
4567
46- 这里可能会疑惑，在递归遍历的时候，什么时候直接return 递归函数的返回值，什么时候不用加这个 return， 这取决于对递归函数的定义，这里定义的递归函数，就是返回 要查找的元素所在的节点，而这个节点就是我们所求，所以直接return递归函数的返回值。
68+ 这里可能会疑惑，在递归遍历的时候，什么时候直接return 递归函数的返回值，什么时候不用加这个 return呢。
69+
70+ 我们在[ 二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？] ( https://mp.weixin.qq.com/s/6TWAVjxQ34kVqROWgcRFOg ) 中讲了，如果要搜索一条边，递归函数就要加返回值，这里也是一样的道理。
71+
72+ ** 因为搜索到目标节点了，就要立即return了，这样才是找到节点就返回（搜索某一条边），如果不加return，就是遍历整棵树了。**
4773
4874整体代码如下：
4975
@@ -56,16 +82,23 @@ TreeNode* searchBST(TreeNode* root, int val) {
5682}
5783```
5884
59- ###迭代法
85+ ##迭代法
86+
87+ 一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。
88+
89+ 对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。
90+
91+ 对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。
92+
93+ 而** 对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。**
6094
61- 一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历，其实因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。
95+ 例如要搜索元素为3的节点， ** 我们不需要搜索其他节点，也不需要做回溯，查找的路径已经规划好了。 **
6296
63- 对于一般二叉树，模拟递归的过程中还有一个回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。
97+ 中间节点如果大于3就向左走，如果小于3就向右走，如图：
6498
65- 看如下图中的这颗二叉搜索树，例如要搜索元素为3的节点，我们不需要搜索其他节点，也不需要做回溯，查找的路径已经规划好了。
6699![ 二叉搜索树] ( https://img-blog.csdnimg.cn/20200812190213280.png )
67100
68- 迭代法代码如下 ：
101+ 所以迭代法代码如下 ：
69102
70103```
71104class Solution {
@@ -81,34 +114,19 @@ public:
81114};
82115```
83116
84- ## C++代码
117+ 第一次看到了如此简单的迭代法，是不是感动的痛哭流涕，哭一会 ~
85118
86- ###递归
87- ```
88- class Solution {
89- public:
90- TreeNode* searchBST(TreeNode* root, int val) {
91- if (root == NULL || root->val == val) return root;
92- if (root->val > val) return searchBST(root->left, val);
93- if (root->val < val) return searchBST(root->right, val);
94- return NULL;
95- }
96- };
97- ```
119+ #总结
120+
121+ 本篇我们介绍了二叉搜索树的遍历方式，因为二叉搜索树的有序性，遍历的时候要比普通二叉树简单很多。
122+
123+ 但是一些同学很容易忽略二叉搜索树的特性，所以写出遍历的代码就未必真的简单了。
124+
125+ 所以针对二叉搜索树的题目，一样要利用其特性。
126+
127+ 文中我依然给出递归和迭代两种方式，可以看出写法都非常简单，就是利用了二叉搜索树有序的特点。
128+
129+ 就酱，如果学到了，就转发给身边需要的同学吧！
98130
99- ###迭代
100- ```
101- class Solution {
102- public:
103- TreeNode* searchBST(TreeNode* root, int val) {
104- while (root != NULL) {
105- if (root->val > val) root = root->left;
106- else if (root->val < val) root = root->right;
107- else return root;
108- }
109- return NULL;
110- }
111- };
112- ```
113131
114132> 更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。