一、标题
给定一个二叉树, 找到该树中两个指定节点的迩来公共先人。
百科中迩来公共先人的界说为：
对于有根树 T 的两个结点 p、q，迩来公共先人表现为一个结点 x，满足 x 是 p、q 的先人且 x 的深度尽可能大（一个节点也可以是它自己的先人）。
二、示例
2.1> 示例 1:
【输入】 root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
【输出】 3
【表明】 节点 5 和节点 1 的迩来公共先人是节点 3。
2.2> 示例 2:
【输入】 root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
【输出】 5
【表明】 节点 5 和节点 4 的迩来公共先人是节点 5。由于根据界说迩来公共先人节点可以为节点自己。
分析：
- 全部节点的值都是唯一的。
- p、q 为差别节点且均存在于给定的二叉树中。
三、解题思绪
根据标题形貌，会给我们两个节点，分别是TreeNode p和TreeNode q，然后我们需要在一个二叉树中去探求着两个给定节点的迩来公共先人。这个题与《剑指 Offer 68 - I. 二叉搜索树的迩来公共先人》很类似，只不外我们这个树是寻常的二叉树，不能利用二叉搜索树的特性来解题了。
那么我们知道，针对某一个节点来说，它是具有左子树和右子树这两个属性的，那么对于随机给出的p节点和q节点来说，就会有如下3种环境，请见下图所示：
根据上图形貌，我们可以得出如下3种环境：
【环境1】当p节点和q节点分别在根节点的左子树和右子树中时，那么根节点就是迩来公共先人节点。
【环境2】当p节点和q节点都在根节点的左子树中时，第一个遍历到的节点就是迩来公共先人节点。
【环境3】当p节点和q节点都在根节点的右子树中时，第一个遍历到的节点就是迩来公共先人节点。
以是，针对上面的分析，我们可以通过深度遍历来遍历二叉树中的节点，当发现某个节点即是p节点大概即是q节点，则制止这一侧子树的遍历。然后当根节点的左子树和右子树都遍历完毕后，再根据以上3种环境，返回这道题的终极结果即可。
解题思绪我们说完了，下面照旧按照惯例，以输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 8为例，看一下具体处置处罚流程是怎么样子的。请见下图所示：
四、代码实现 |
