代码随想录算法训练营第二十天｜ 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先

●  530.二叉搜索树的最小绝对差 

题目：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/submissions/

解答：https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html

递归：

1. 最直观的想法，就是把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了

2. 直接计算：需要用一个pre节点记录一下cur节点的前一个节点

迭代

●  501.二叉搜索树中的众数 

题目：https://leetcode.cn/problems/find-mode-in-binary-search-tree/

解答：https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

如果不是二叉搜索树：

如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。把map转化数组即vector，再进行排序。

此时数组vector中已经是存放着按照频率排好序的pair，那么把前面高频的元素取出来就可以了

是二叉搜索树：

既然是搜索树，它中序遍历就是有序的。遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了

弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。

而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素。

只需要遍历一次就可以找到所有的众数：

如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中

频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了

●  236. 二叉树的最近公共祖先  

题目：https://leetcode.cn/problems/find-mode-in-binary-search-tree/

解答：https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html

那么我给大家归纳如下三点：

求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。

在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。

要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。