一、标题
给定一个二叉搜索树, 找到该树中两个指定节点的迩来公共先人。
百科中迩来公共先人的界说为：
对于有根树 T 的两个结点 p、q，迩来公共先人体现为一个结点 x，满意 x 是 p、q 的先人且 x 的深度尽大概大（一个节点也可以是它自己的先人）。
二、示例
2.1> 示例 1:
【输入】 root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
【输出】 6
【解释】 节点 2 和节点 8 的迩来公共先人是 6。
2.2> 示例 2:
【输入】 root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
【输出】 2
【解释】 节点 2 和节点 4 的迩来公共先人是 2, 因为根据界说迩来公共先人节点可以为节点自己。
分析：
- 全部节点的值都是唯一的。
- p、q 为差异节点且均存在于给定的二叉搜索树中。
三、解题思绪
根据标题形貌，我们给我们两个节点TreeNode p和TreeNode q，然后在二叉搜索树中去探求迩来公共先人。那么标题中给出了非常关键的一个信息就是——二叉搜索树，那么这种二叉树具有如下的特征：
【若它的左子树不空】则左子树上全部结点的值均小于它的根结点的值；
【若它的右子树不空】则右子树上全部结点的值均大于它的根结点的值；
以是针对如上特点，我们可以根据TreeNode p和TreeNode q这两个树节点处于二叉搜索树差异位置来总结出如下的3种情况：
根据上图形貌，我们可以得出如下3种情况：
【情况1】当根节点的值处于p节点的值和q节点的值之间时，那么根节点就是迩来公共先人节点。
【情况2】当根节点的值大于p节点的值和q节点的值时，那么我们只必要遍历根节点的左子树，然后第一个遍历到的节点就是迩来公共先人节点。
【情况3】当根节点的值小于p节点的值和q节点的值时，那么我们只必要遍历根节点的右子树，然后第一个遍历到的节点就是迩来公共先人节点。
【留意】每当遍历到一个子树的根节点时，都必要对比上面的3种情况，来决定实行那块逻辑。
上面就是具体的解题思绪了，下面我们以输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4为例，看一下具体的处理惩罚过程。请见下图所示：
四、代码实现 |
