继续创造，加速成长！这是我参与「日新方案 10 月更文应战」的第31天，点击查看活动概况
标题描绘
给定一个二叉树, 找到该树中两个指定节点的最近公共先人。
百度百科中最近公共先人的界说为：“关于有根树 T 的两个结点 p、q，最近公共先人表示为一个结点 x，满意 x 是 p、q 的先人且 x 的深度尽可能大（一个节点也可所以它自己的先人）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共先人是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共先人是节点 5。因为依据界说最近公共先人节点能够为节点自身。
说明:
- 一切节点的值都是仅有的。
- p、q 为不同节点且均存在于给定的二叉树中。
原题链接：leetcode.cn/problems/er…
解题思路
这题官方给出的难度等级是简略，我个人认为这题在简略题里应该算是比较难的了 （可能是我比较菜） 。
我的思路是用递归dfs的方式，找到每个节点及它基层的节点中满意条件的节点个数，在回溯的时分判别找到的节点个数是否等于2，就能够找出第一个公共父节点。
具体步骤：
- 先保存要寻觅的节点q和p，别弄丢了，因为这两个节点是后面每层递归都要用的，所以我选择用全局变量来保存，一同界说全局变量ans用来保存答案。
- 界说递归的停止条件，当时节点为null的时分就需要停止了。
- 界说count用于存储符合条件的节点个数，因为咱们在递归的时分只判别当时这一层和基层节点的个数，故count在递归中界说为0即可。
- 判别当时节点是否满意条件，标题中现已告诉咱们每个节点的值都是不一样的了，所以咱们直接用节点值判别即可，并且不需要担心重复值搅扰count的情况。若满意就把count+1。
- 递归左子树和右子树，获取他们当中满意条件的节点个数，并一同加到count当中。这样一来，count就等于当时节点和一切基层节点中满意条件的个数了。
- 判别当时count值，是否等于2，等于2就说明现已找到q和p两个节点了，那当时节点必定就是公共节点了。但这里要注意，咱们只需要找到最近的那个公共先人，因为递归是往上回溯的，所以第一个count==2的节点就是最近的公共先人。为了避免上层节点重复赋值，所以咱们一同要判别ans是否为null。
- 递归完毕后，答案现已被存到ans中了，咱们直接返回ans即可。
- 配合下面的AC代码来理解解题思路更佳噢~
Java AC代码：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 把值存起来，便于后面核算
this.q = q;
this.p = p;
this.ans = null;
dfs(root);
return ans;
}
TreeNode q, p, ans;
public int dfs(TreeNode now) {
// 停止条件
if (now == null) return 0;
// count 用于记录本层和本层以下的一切满意条件的节点个数
int count = 0;
// 判别当时节点是否满意条件
if ( now.val == p.val || now.val == q.val ) {
count++;
}
// 判别下面几层的节点满意条件的个数
count += dfs(now.left);
count += dfs(now.right);
// 假如满意条件的个数为2，且ans还没有被赋值
// 说明这是第一个公共父节点，故把它存起来
if (count == 2 && ans == null) {
ans = now;
}
return count;
}
}
运转速度还不错
标题分享
别的还有一道跟这题有点像的标题，也一同分享给咱们：160. 相交链表 – 力扣（LeetCode）
这道相交链表其实也能够当作一个“二叉树”找最近的公共节点，只不过这个“二叉树”是尾巴节点指向头节点的，而咱们正常二叉树是头节点指向子树节点的，所以这两道题其实解题思路是不同的，有爱好的同学能够练习一下噢。
