腾讯精选50题算法【二叉搜索树的最近公共祖先】
最近几周掺杂着需求、以及一些琐碎的事情，算法的学习一直都是默默的在搞，没有形成文章。
或许是我懒惰了；或许是我松懈了；或许是我不重视了；但是，我还在。学习可能会因为工作推迟，但绝不会迟到，所以，还请各位放心，该有的都会到来。为了补偿下，文末送个双十二大福利，知识星球优惠券
之前也在有些群里看到算法的持续学习，我自己又找了一个方式来攻克LeetCode上的题目，先从腾讯精选练习（50题） 开始，之前有完成过一些，不过都是整合在ARTS打卡里，也没细说。现在是一个系列，还有机会学习哒。
Algorithm LeetCode算法
235. 二叉搜索树的最近公共祖先
(https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)
题目描述：给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
6
/ \
2 8
/ \ / \
0 4 7 9
/ \
3 5示例1：
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。示例2：
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。在题解之前，我们还是有必要知道二叉搜索树是一颗什么样的树，都有什么特点。
二叉搜索树（Binary Search Tree），又（二叉查找树，二叉排序树）它或者是一颗空树，或者是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树分别为二叉排序树。
最近公共祖先： 是距离两个节点最近的公共祖先节点。在这里最近考虑的是节点的深度。
比如，在我们这颗二叉树中
- 如果p是2，q是8的情况，分别在跟节点的左右两边，则最近的公共节点就是他们的根节点，即6；
- 如果p是2，q是7的情况，因为还是分别在6这个根节点的左右两边，那最近的公共节点还是6；
- 如果p是2，q是4的情况，2和4在节点2的右子树上，即最小公共节点就是2自己了（一个节点也可以是它自己的祖先）
- 如果p是2，q是0的情况，2和0在节点2的左子树上，即最小公共节点还是2自己
好了，搞清楚了各种情况，接下来的解法肯定就难不倒我们了。写代码是建立在思路清晰的基础上，对吧。
解法：递归
- 从根节点开始遍历
- 倘若p和q都在右子树上，则以右孩子为根节点继续1的操作
- 倘若p和q都在左子树上，则以左孩子为根节点继续1的操作
- 如果步骤2和步骤3均不成立，则说明我们已经找到答案
将二叉树构建完成：
// 将二叉树构建完成
public static void main(String[] args) {
TreeNode treeNode = new TreeNode(6);
treeNode.left = new TreeNode(2);
treeNode.left.left = new TreeNode(0);
treeNode.left.right = new TreeNode(4);
treeNode.left.right.left = new TreeNode(3);
treeNode.left.right.right = new TreeNode(5);
treeNode.right = new TreeNode(8);
treeNode.right.left = new TreeNode(7);
treeNode.right.right = new TreeNode(9);
TreeNode treeNode2 = lowestCommonAncestor(treeNode, new TreeNode(2), new TreeNode(8));
System.out.println(treeNode2);
}递归查找二叉树：
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int parent = root.val;
int pValue = p.val;
int qValue = q.val;
// 如果两个值都大于跟节点，则从右子树查找
if (pValue > parent &&qValue > parent) {
return lowestCommonAncestor(root.right, p, q);
// 如果两个值都小于跟节点，则从左子树查找
} else if (pValue < parent && qValue < parent) {
return lowestCommonAncestor(root.left, p, q);
// 上述两种情况均没有，则得到答案
} else {
return root;
}
}这里仅仅举例说明了通过递归的方式来解题，基本上也都能解决二叉树相关的问题。但是，就这样就够了吗？其实并没有，二叉树也有自己的特性，有时候是不需要通过递归来解决的。
在我们这个题解里，时间复杂度是O(N)，空间复杂度是O(N),时间复杂度没办法了，N是节点中的个数，在最坏的情况下我们是需要访问所有的节点，但是我们可以优化空间复杂度。
递归的时候，额外空间主要是栈产生的，N就是二叉树的高度，最坏情况下就是访问所有的，但是我们可以通过另一种方式来优化，空间复杂度可以达到O(1)。欢迎在留言区和我互动，至于写法，我会在知识星球给出，加入星球的小伙伴直接去看就行啦。
结语
二叉搜索树，算是对二叉树的一个延伸了，但是呢，解题的思路还是大同小异，无非就是二叉搜索树更加有自己的特点，我们操作起来反而会目的性更明确一些，也更好去理解。
LeetCode真的是一个好的学习社区，无论在谁的眼里，都是学习算法的好去处。小编也无数次的说过，算法就是一个持续学习的过程，只要持续学习，持续练习，持续写代码，你就能懂其中的解法，对于我们程序员的思维来说，是一个极大的提升，欢迎和大家一起学习。
插播一条
彪悍一只猫说过：他的很多次成为第一的经历，最主要的还是来自于社群的力量，如果没有来自社群的支持，他的推广能力是有限的，要想拿第一，真的很难。
所以，做好一个品牌，需要社群的力量，然后加上后期的IP推广。万事开头难，我现在需要的还是第一步，培养自己的社群，创造属于自己的一个小家庭，让每个人都有参与感，都能感受到存在的价值。
所以，在建立微信群的基础上，我也把星球建立起来了，就是为了和大家有更多的知识、职场等的交流。我个人还喜欢看球，还希望和大家一起聊聊球，畅所欲言呢。