530.二叉搜索树的最小绝对差
题目链接：530.二叉搜索树的最小绝对差
文档讲解：代码随想录
状态：根据二叉搜索树性质轻松AC，本题对于返回值的思考，以及对于传统递归的思辨
思路
与之前题目类似，利用二叉搜索树的中序遍历性质解决：
最小差值一定存在于单调数组相邻两个元素中，采用经典的pre指针解决
所谓中序遍历中的中，就是处理节点的位置在left与right的中间，二叉树递归遍历的本质都是在于处理中间节点。
注意！本题不可使用传统的递归，因为最小值不一定是当前节点与左右节点的差值，要充分利用性质解决问题。
题解
//本题目利用中序遍历，注意思考返回值int的使用
class Solution {
public:
int res = INT_MAX;
TreeNode* pre;
int getMinimumDifference(TreeNode* root) {
//这个可以随机给，因为终止条件并不构成结果的一部分，完成return的功能即可
if(root == nullptr)return INT_MAX;
//本题需要的是中序遍历，在相邻前后比较。而不是传统意义上递归获得左边绝对值之差
getMinimumDifference(root->left);
//二叉搜索树的关键处理，首先判断pre!=nullptr，这是上一步回溯的到的pre节点
if(pre!=nullptr && res>abs(root->val-pre->val))res = abs(root->val-pre->val);
//对pre使用后再更新
pre = root;
getMinimumDifference(root->right);
return res;
}
};
501.二叉搜索树中的众数
题目链接：501.二叉搜索树中的众数
文档讲解：代码随想录
状态：对于返回情况糊涂，出现bug
思路
补充：对于普通二叉树的众数：采用map采集所有数据以及他们的次数，关键在于排序。
对于map的排序介绍:
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int> a , pair<int,int> b)
{
//增序为 a.first<b.first(若是想排序的第二个数字，把first改成second即可）
return a.first>b.first;
}
int main()
{
map<int,int> s;
s[1]=4;
s[2]=3;
s[3]=6;
s[4]=7;
s[5]=1;
//利用vector容器储存后再进行排序。
vector< pair<int,int> > v(s.begin(),s.end());
sort(v.begin(),v.end(),cmp);
for(vector< pair<int,int> >::iterator it=v.begin();it!=v.end();++it)
cout<<it->first<<" "<<it->second<<endl;
/*打印结果：
5 1
4 7
3 6
2 3
1 4
*/
}
对于二叉搜索树，利用性质其实就变成了一个模拟题，看题解即可，关键注意当count>max_count时vector的清空，以及max_count、count赋值的统一性。
题解
class Solution {
public:
int max_count = 1;
int count = 1;
TreeNode* pre = nullptr;
vector<int> res;
vector<int> findMode(TreeNode* root) {
if(root == nullptr)return res;//同样返回啥都可以，仅作为终止条件
//中序遍历仅作为方向，不用返回值，这个在二叉搜搜索树中特别常用
findMode(root->left);
if(pre!=nullptr&&root->val == pre->val)count++;
else if(pre!=nullptr && root->val != pre->val)count = 1;
if(count == max_count)res.push_back(root->val);
else if(count>max_count)
{
max_count = count;
res.clear();
res.push_back(root->val);
}
pre = root;
findMode(root->right);
return res;
}
};
236.二叉树的最近公共祖先
题目链接：236.二叉树的最近公共祖先
文档讲解：代码随想录
状态：边看题解边做的，掌握新方法
思路
首先根据题目和用例搞清最近公共祖先的含义：
本题的递归是传统的递归，结果是从下至上传递，与递归的顺序相符合，如下图：
其实感觉这个题目有点文字游戏，题目给的条件很多*，p 、q 一定存在且不相同，节点数量大于2，所有的节点互不相同。
简单说，根据递归从下到上查找（后序遍历），遇到结果返回（不需要知道是哪个结果），遇到两个结果返回->这里引出了本题令人糊涂的点，多个返回值，要弄清楚先后顺序，因为一个点，首先判断他是不是答案
学习分类思考，理清全部清空，比如当前节点是p、q中一个，那么假如另一个在前、在后有什么影响？返回什么？在脑子里想清楚。
题解
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr || root == p || root == q)return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
//先判断自己
if(left!=nullptr&&right!=nullptr)return root;
//如果自己不是再传递
else if(left!=nullptr)return left;
else if(right!=nullptr)return right;
else return nullptr;
}
};