【20200927 每日一题】刷题使我快乐。更多LeetCode答案请见我的 GitHub。

今天 3 个题解已上传至此文件夹。236的两个解法对于235都是适用的。

235. 二叉搜索树的最近公共祖先
难度简单
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,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, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

看到这道题，我很开心，因为我以为这道题是我做过的 236. 二叉树的最近公共祖先。这道题我在之前的总结文章 10分钟速查LeetCode 热题100 中等 里面就已经讲过了。

等等！

这可是二叉搜索树，它的左子树上的值都小于根节点，右子树上的值都大于根节点。可不可以利用这个办法让它变得简单一点呢？

当然可以啦。

首先我们假设

p

那么由于值的唯一性，root.val只有三种可能

• root.val<p.val
• p.val<=root.val && root.val<=q.val
• root.val<q.val

第一种情况呢，显然我们要去比root值都要小的的左子树root.left上查找，所以只需要

return 

第三种情况呢，和第一种情况是对称的。

return 

第二种情况呢，直接 return root就可以了。

你可能会说，在大于p小于q的节点可能有很多很多个呢，为啥这样写就是对的？

因为这样写的顺序是dfs的顺序，遇到第一个满足这个条件的必然是它们的祖先。

好了，那么如果假设 p.val<q.val 不成立怎么办？

那还不简单，就把它们交换一下咯~（不交换也可以啊，只是筛选条件写得稍微复杂一点。）

/**

我们再来看236题。

236. 二叉树的最近公共祖先
难度中等
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

现在我们失去二叉搜索树的特性了，这题还能做嘛？

当然可以啦。

解法一 dfs 递归

这种解法我在我的另一篇文章 10分钟速查LeetCode 热题100 中等 里提到过，引用一下。

dfs(root, p, q)返回值只有1和0。
1：以root为根节点的子树包含至少一个p或者q。
0：以root为根节点的子树既不包含p也不包含q。
当left+right+mid>1时，说明以root为根节点的子树的左孩子子树/右孩子子树/root中的2个部分分别包含p和q，此时是最短路径了，记录ancestor。再继续递归，p和q就不可避免地会长在以新的root节点为根的一棵子树上，此时再也无法出现left+right+mid>1的情况的了。

class 

解法二 bfs，迭代

map中储存的都是父节点，通过bfs遍历所有节点找到所有节点的父节点之后呢，我们就把p的所有父节点（包括本身），全部加进set，然后就从q的父节点往上找，找到第一个set包含的节点，就是最低的公共祖先啦。

注意最开始要写

map

这会是后面循环的终止条件。

/**

然后这道题又让我想起了之前Princeton公开课写过的一道作业，同样是查找公共祖先，但是每一个节点可能有多个公共祖先，这种情况要怎么查找呢？

• 原题目在此（英文的）
• 我的代码在此，是的你没看错，要求通过三个java文件实现。

如果有五个人点赞，我就写一写。。。。

以上。