530.二叉搜索树的最小绝对差
卡哥建议：需要领悟一下二叉树遍历上双指针操作，优先掌握递归
题目链接/文章讲解：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
做题思路：
注意是二叉搜索树，二叉搜索树可是有序的。
遇到在二叉搜索树上求什么最值啊，差值之类的，最直观的想法，就是把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了。
双指针法需要用一个pre节点记录一下cur节点的前一个节点。比如，一开始，cur是根节点，pre是空节点，中序遍历的话，cur->left，cur会指向左子树，这时候就需要用pre = cur，来保存住cur指向的左孩子节点，也就是前一个遍历过的节点，看卡哥文章的图。
本题代码：
1 class Solution {
2 private:
3 int result = INT_MAX;
4 TreeNode* pre = NULL;
5 void traversal(TreeNode* cur) {
6 if (cur == NULL) return;
7 traversal(cur->left); // 左
8 if (pre != NULL){ // 中
9 result = min(result, cur->val - pre->val);
10 }
11 pre = cur; // 记录前一个
12 traversal(cur->right); // 右
13 }
14 public:
15 int getMinimumDifference(TreeNode* root) {
16 traversal(root);
17 return result;
18 }
19 };
501.二叉搜索树中的众数
卡哥建议：和 530差不多双指针思路，不过 这里涉及到一个很巧妙的代码技巧。可以先自己做做看，然后看我的视频讲解。
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
视频讲解：https://www.bilibili.com/video/BV1fD4y117gp
做题思路：
既然是搜索树，它中序遍历就是有序的。遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了。
双指针法：弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素。因为此时cur是当前比较的第一个元素，没有前一个。
题目要求最大频率的元素集合（注意是集合，不是一个元素，可以有多个众数），如果是数组上应该是先遍历一遍数组，找出最大频率（maxCount），然后再重新遍历一遍数组把出现频率为maxCount的元素放进集合。（因为众数有多个）这种方式遍历了两遍数组。那么我们遍历两遍二叉搜索树，把众数集合算出来也是可以的。但这里其实只需要遍历一次就可以找到所有的众数。
如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中；
如果频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集，因为结果集之前的元素都失效了。
本题代码：
1 class Solution {
2 private:
3 int maxCount = 0; // 最大频率
4 int count = 0; // 统计频率
5 TreeNode* pre = NULL;
6 vector<int> result;
7 void searchBST(TreeNode* cur) {
8 if (cur == NULL) return ;
9
10 searchBST(cur->left); // 左
11 // 中
12 if (pre == NULL) { // 第一个节点
13 count = 1;
14 } else if (pre->val == cur->val) { // 与前一个节点数值相同
15 count++;
16 } else { // 与前一个节点数值不同
17 count = 1;
18 }
19 pre = cur; // 更新上一个节点
20
21 if (count == maxCount) { // 如果和最大值相同，放进result中
22 result.push_back(cur->val);
23 }
24
25 if (count > maxCount) { // 如果计数大于最大值频率
26 maxCount = count; // 更新最大频率
27 result.clear(); // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
28 result.push_back(cur->val);
29 }
30
31 searchBST(cur->right); // 右
32 return ;
33 }
34
35 public:
36 vector<int> findMode(TreeNode* root) {
37 count = 0;
38 maxCount = 0;
39 TreeNode* pre = NULL; // 记录前一个节点
40 result.clear();
41
42 searchBST(root);
43 return result;
44 }
45 };
236. 二叉树的最近公共祖先
卡哥建议：本题其实是比较难的，可以先看我的视频讲解
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
视频讲解：https://www.bilibili.com/video/BV1jd4y1B7E2
做题思路：
如何判断一个节点是节点q和节点p的公共祖先呢。
首先最容易想到的一个情况：如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。 即情况一：
判断逻辑是 如果递归遍历遇到q，就将q返回，遇到p 就将p返回，那么如果 左右子树的返回值都不为空，说明此时的中节点，一定是q 和p 的最近祖先。
但是很多人容易忽略一个情况，就是节点本身p(q)，它拥有一个子孙节点q(p)。 情况二：
其实情况一 和 情况二 代码实现过程都是一样的，也可以说，实现情况一的逻辑，顺便包含了情况二。因为遇到 q 或者 p 就返回，这样也包含了 q 或者 p 本身就是 公共祖先的情况。
本题代码：
1 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
2 if (root == q || root == p || root == NULL) return root;
3 TreeNode* left = lowestCommonAncestor(root->left, p, q);
4 TreeNode* right = lowestCommonAncestor(root->right, p, q);
5 if (left != NULL && right != NULL) return root;
6
7 if (left == NULL && right != NULL) return right;
8 else if (left != NULL && right == NULL) return left;
9 else { // (left == NULL && right == NULL)
10 return NULL;
11 }
12
13 }