530.二叉搜索树中的最小绝对值差
因为二叉树的中序遍历是有序递增序列,因此,本题可以直接进行中序遍历,然后用双指针法比较相邻两个节点直接的差值,并更新差值的最小值,最后得到结果!
二叉搜索树 == 有序数组,遇到在二叉搜索树上求什么最值啊,差值之类的,就把它想成在一个有序数组上求最值,求差值,这样就简单多了。
501.二叉搜索树中的众数
//涉及到二叉搜索树,要联想到中序遍历,并且联想到双指针思路!
//涉及到频率,要联想到哈希法记录数值重复出现的次数。
//涉及到二叉搜索树中重复出现的数,一定是相邻的!
//关键步骤:
if (pre == nullptr) count = 1;
else if (pre->val == node->val) count++;
else if (pre->val != node->val) count = 1;
pre = node;
if (count == maxCount) res.push_back(node->val);
else if (count > maxCount) {
maxCount = count;
res.clear();
res.push_back(node->val);
}
236.二叉树的最近公共祖先
二叉树的公共祖先涉及到 回溯 的过程(也就是自底向上查询/返回的过程),而回溯一定要用到 后序遍历了!因为后序遍历(左右中)就是天然的回溯过程,可以根据左右子树的返回值,来处理中节点的逻辑。
本题:判断逻辑是 如果递归遍历遇到q,就将q返回,遇到p 就将p返回,那么如果 左右子树的返回值都不为空,说明此时的中节点,一定是q 和p 的最近祖先。
本题归纳如下三点:
-
求最小公共祖先,需要从底向上遍历,那么二叉树,只能通过后序遍历(即:回溯)实现从底向上的遍历方式。
-
在回溯的过程中,必然要遍历整棵二叉树,即使已经找到结果了,依然要把其他节点遍历完,因为要使用递归函数的返回值(也就是代码中的left和right)做逻辑判断。
-
要理解如果返回值left为空,right不为空为什么要返回right,为什么可以用返回right传给上一层结果。
可以说这里每一步,都是有难度的,都需要对二叉树,递归和回溯有一定的理解。