11##链接
22https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
33
4- ##思路
4+ > 二叉搜索树的最近公共祖先问题如约而至
5+
6+ #235. 二叉搜索树的最近公共祖先
7+
8+ 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
9+
10+ 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
11+
12+ 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
513
14+ 例如，给定如下二叉搜索树: root = [ 6,2,8,0,4,7,9,null,null,3,5]
615
7- 遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了，可惜二叉树只能自上向低。
16+ ![ 235. 二叉搜索树的最近公共祖先 ] ( https://img-blog.csdnimg.cn/20201018172243602.png )
817
9- 那么自上相下查找的话，如何记录祖先呢？
18+ 示例 1:
1019
11- 做过[ 236. 二叉树的最近公共祖先] ( https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/ ) 题目的同学，应该知道，只要判断一个节点的左子树里有p，右子树里有q，那么当前节点就是最近公共祖先。
20+ 输入: root =[ 6,2,8,0,4,7,9,null,null,3,5] , p = 2, q = 8
21+ 输出: 6
22+ 解释: 节点 2 和节点 8 的最近公共祖先是 6。
23+ 示例 2:
24+
25+ 输入: root =[ 6,2,8,0,4,7,9,null,null,3,5] , p = 2, q = 4
26+ 输出: 2
27+ 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
28+
29+
30+ 说明:
31+
32+ * 所有节点的值都是唯一的。
33+ * p、q 为不同节点且均存在于给定的二叉搜索树中。
34+
35+ ##思路
36+
37+ 做过[ 二叉树：公共祖先问题] ( https://mp.weixin.qq.com/s/n6Rk3nc_X3TSkhXHrVmBTQ ) 题目的同学应该知道，利用回溯从底向上搜索，遇到一个节点的左子树里有p，右子树里有q，那么当前节点就是最近公共祖先。
1238
1339那么本题是二叉搜索树，二叉搜索树是有序的，那得好好利用一下这个特点。
1440
1541在有序树里，如果判断一个节点的左子树里有p，右子树里有q呢？
1642
17- 其实只要从上到下遍历的时候，如果 (p->val <= cur->val && cur->val <= q->val)则说明该节点cur就是最近公共祖先了。
43+ 其实只要从上到下遍历的时候，cur节点是数值在[ p, q] 区间中则说明该节点cur就是最近公共祖先了。
44+
45+ 理解这一点，本题就很好解了。
46+
47+ 和[ 二叉树：公共祖先问题] ( https://mp.weixin.qq.com/s/n6Rk3nc_X3TSkhXHrVmBTQ ) 不同，普通二叉树求最近公共祖先需要使用回溯，从底向上来查找，二叉搜索树就不用了，因为搜索树有序（相当于自带方向），那么只要从上向下遍历就可以了。
1848
19- 理解这一点，本题就很好解了 。
49+ 那么我们可以采用前序遍历（其实这里没有中节点的处理逻辑，遍历顺序无所谓了） 。
2050
21- 如图所示
51+ 如图所示：p为节点3，q为节点5
2252
2353<img src =' ../pics/235.二叉搜索树的最近公共祖先.png ' width =600 > </img ></div >
2454
25- 在遍历二叉搜索树的时候就是寻找区间[ p->val, q->val] （注意这里是左闭又闭）
55+ 可以看出直接按照指定的方向，就可以找到节点4，为最近公共祖先，而且不需要遍历整棵树，找到结果直接返回！
56+
2657
27- 那么如果 cur->val 大于 p->val，同时 cur->val 大于q->val，那么就应该向左遍历。（因为我们此时不知道p和q谁大，所以两个都要判断）
58+ 递归三部曲如下：
59+
60+ * 确定递归函数返回值以及参数
61+
62+ 参数就是当前节点，以及两个结点 p、q。
63+
64+ 返回值是要返回最近公共祖先，所以是TreeNode * 。
2865
2966代码如下：
3067
3168```
32- if (cur->val > p->val && cur->val > q->val) {
33- return traversal(cur->left, p, q);
34- }
69+ TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)
3570```
3671
37- 如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历。
72+ * 确定终止条件
73+
74+ 遇到空返回就可以了，代码如下：
3875
3976```
40- } else if (cur->val < p->val && cur->val < q->val) {
41- return traversal(cur->right, p, q);
42- }
77+ if (cur == NULL) return cur;
4378```
4479
45- 剩下的情况，我们就找到了区间使（p->val <= cur->val && cur->val <= q->val）或者是 （q->val <= cur->val && cur->val <= p->val）
80+ 其实都不需要这个终止条件，因为题目中说了p、q 为不同节点且均存在于给定的二叉搜索树中。也就是说一定会找到公共祖先的，所以并不存在遇到空的情况。
81+
82+ * 确定单层递归的逻辑
83+
84+ 在遍历二叉搜索树的时候就是寻找区间[ p->val, q->val] （注意这里是左闭又闭）
85+
86+ 那么如果 cur->val 大于 p->val，同时 cur->val 大于q->val，那么就应该向左遍历（说明目标区间在左子树上）。
87+
88+ ** 需要注意的是此时不知道p和q谁大，所以两个都要判断**
4689
4790代码如下：
91+
4892```
49- else {
50- return cur;
51- }
93+ if (cur->val > p->val && cur->val > q->val) {
94+ TreeNode* left = traversal(cur->left, p, q);
95+ if (left != NULL) {
96+ return left;
97+ }
98+ }
99+ ```
100+
101+ ** 细心的同学会发现，在这里调用递归函数的地方，把递归函数的返回值left，直接return** 。
102+
103+
104+ 在[ 二叉树：公共祖先问题] ( https://mp.weixin.qq.com/s/n6Rk3nc_X3TSkhXHrVmBTQ ) 中，如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树。
105+
106+ 搜索一条边的写法：
52107
53108```
109+ if (递归函数(root->left)) return ;
54110
55- 那么整体递归代码如下:
111+ if (递归函数(root->right)) return ;
112+ ```
56113
57- ## C++递归代码
114+ 搜索整个树写法：
58115
59- （我这里特意把递归的过程抽出一个函数traversal，这样代码更清晰，有助于读者理解。）
116+ ```
117+ left = 递归函数(root->left);
118+ right = 递归函数(root->right);
119+ left与right的逻辑处理;
120+ ```
121+
122+ 本题就是标准的搜索一条边的写法，遇到递归函数的返回值，如果不为空，立刻返回。
123+
124+
125+ 如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历（目标区间在右子树）。
126+
127+ ```
128+ if (cur->val < p->val && cur->val < q->val) {
129+ TreeNode* right = traversal(cur->right, p, q);
130+ if (right != NULL) {
131+ return right;
132+ }
133+ }
134+ ```
135+
136+ 剩下的情况，就是cur节点在区间（p->val <= cur->val && cur->val <= q->val）或者 （q->val <= cur->val && cur->val <= p->val）中，那么cur就是最近公共祖先了，直接返回cur。
137+
138+ 代码如下：
139+ ```
140+ return cur;
141+
142+ ```
143+
144+ 那么整体递归代码如下:
60145
61146```
62147class Solution {
63148private:
64149 TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
65- if (cur->val > p->val && cur->val > q->val) {
66- return traversal(cur->left, p, q);
67- } else if (cur->val < p->val && cur->val < q->val) {
68- return traversal(cur->right, p, q);
69- } else return cur;
150+ if (cur == NULL) return cur;
151+ // 中
152+ if (cur->val > p->val && cur->val > q->val) { // 左
153+ TreeNode* left = traversal(cur->left, p, q);
154+ if (left != NULL) {
155+ return left;
156+ }
157+ }
158+
159+ if (cur->val < p->val && cur->val < q->val) { // 右
160+ TreeNode* right = traversal(cur->right, p, q);
161+ if (right != NULL) {
162+ return right;
163+ }
164+ }
165+ return cur;
70166 }
71167public:
72168 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
73-
74169 return traversal(root, p, q);
75170 }
76171};
77172```
78173
174+ 精简后代码如下：
175+
176+ ```
177+ class Solution {
178+ public:
179+ TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
180+ if (root->val > p->val && root->val > q->val) {
181+ return lowestCommonAncestor(root->left, p, q);
182+ } else if (root->val < p->val && root->val < q->val) {
183+ return lowestCommonAncestor(root->right, p, q);
184+ } else return root;
185+ }
186+ };
187+ ```
188+
189+ ##迭代法
190+
191+ 对于二叉搜索树的迭代法，大家应该在[ 二叉树：二叉搜索树登场！] ( https://mp.weixin.qq.com/s/vsKrWRlETxCVsiRr8v_hHg ) 就了解了。
79192
80- ## C++迭代法代码
193+ 利用其有序性，迭代的方式还是比较简单的，解题思路在递归中已经分析了。
81194
82- 同时给出一个迭代的版本，思想是一样的，代码如下 ：
195+ 迭代代码如下 ：
83196
84197```
85198class Solution {
@@ -96,3 +209,15 @@ public:
96209 }
97210};
98211```
212+
213+ 灵魂拷问：是不是又被简单的迭代法感动到痛哭流涕？
214+
215+ #总结
216+
217+ 对于二叉搜索树的最近祖先问题，其实要比[ 普通二叉树公共祖先问题] ( https://mp.weixin.qq.com/s/n6Rk3nc_X3TSkhXHrVmBTQ ) 简单的多。
218+
219+ 不用使用回溯，二叉搜索树自带方向性，可以方便的从上向下查找目标区间，遇到目标区间内的节点，直接返回。
220+
221+ 最后给出了对应的迭代法，二叉搜索树的迭代法甚至比递归更容易理解，也是因为其有序性（自带方向性），按照目标区间找就行了。
222+
223+ ** 就酱，学到了，就转发给身边需要学习的同学吧！**