● 530.二叉搜索树的最小绝对差
题目:https://leetcode.cn/problems/minimum-absolute-difference-in-bst/submissions/
递归:
1. 最直观的想法,就是把二叉搜索树转换成有序数组,然后遍历一遍数组,就统计出来最小差值了
2. 直接计算:需要用一个pre节点记录一下cur节点的前一个节点
迭代
● 501.二叉搜索树中的众数
题目:https://leetcode.cn/problems/find-mode-in-binary-search-tree/
如果不是二叉搜索树:
如果不是二叉搜索树,最直观的方法一定是把这个树都遍历了,用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/
那么我给大家归纳如下三点:
求最小公共祖先,需要从底向上遍历,那么二叉树,只能通过后序遍历(即:回溯)实现从底向上的遍历方式。
在回溯的过程中,必然要遍历整棵二叉树,即使已经找到结果了,依然要把其他节点遍历完,因为要使用递归函数的返回值(也就是代码中的left和right)做逻辑判断。
要理解如果返回值left为空,right不为空为什么要返回right,为什么可以用返回right传给上一层结果。