二叉搜索树的最小绝对差
思路1：将二叉搜索树转化成一个有序数组，在有序数组上求两个数的最小值差。
只需要遍历有序数组，统计出最小值差
class Solution{
private:
vector<int>vec;
void traversal(TreeNode* root){
if(root == NULL)return;
traversal(root->left);
vec.push_back(root->val);//将二叉搜索树转化成有序数组
traversal(root->right);
}
public:
int getMinimumDifference(TreeNode* root){
vec.clear();
traversal(root);
if(vec.size()<2)return 0;
int result = INT_MAX;
for(int i = 1; i < vec.size();i++){
result = min(result,vec[i] - vec[i - 1]);
}
return result;
}
};思路2：一遍用中序遍历，一边计算差值，需要用一个pre节点记录cur节点的前一个节点。
class Solution{
private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur){
if(cur == NULL)return;
traversal(cur->left);
if(pre != NULL){
result = min(result,cur->val - pre->val);
}
pre = cur;//记录前一个
traversal(cur->right);//右
}
public:
int getMinimumDifference(TreeNode* root){
traversal(root);
return result;
}
};中序遍历的一种迭代法
class Solution{
public:
int getMinimumDifference(TreeNode* root){
stack<TreeNode*>st;
TreeNode* cur = root;
TreeNode* pre = NULL;
int result = INT_MAX;
while(cur != NULL || !st.empty()){
if(cur != NULL){//指针访问节点到最底层
st.push(cur);//将访问的节点放进栈
cur = cur->left;
}else{
cur = st.top();
st.pop();
if(pre != NULL){
result = min(result,cur->val - pre->val);
}
pre = cur;
cur = cur->right;
}
}
return result;
}
};二叉搜索树的特点“有序”！！！递归遍历中前后两个指针的记录！！！
二叉搜索树中的众数
1.不是二叉搜索树的话，把树遍历，用map统计频率，将频率进行排序，最后取前面高频的元素的集合。
>>遍历方法任选
>>对map里频率进行排序
>>取前面高频的元素
class Solution{
preivate:
void searchBST(TreeNode* cur,unordered_map<int,int>&map){//前序遍历
if(cur == NULL)return;
map[cur->val]++;//统计元素频率
search(cur->left,map);
search(cur->right,map);
return ;
}
bool static cmp(const pair<int,int>& a,const pair<int,int>& b){
return a.second > b.second;
}
public:
vector<int>findMode(TreeNode* root){
unordered_map<int,int>map;
vector<int>result;
if(root == NULL)return result;
searchBST(root,map);
vector<pair<int,int>>vec(map.begin(),map.end());
sort(vec.begin(),vec.end(),cmp);
result.push_back(vec[0].first);
for(int i = 1;i < vec.size(); i++){
//取最高的放到result数组中
if(vec[i].second == vec[0].second)result.push_back(vec[i].first);
else break;
}
return result;
}
}2.是二叉搜索树，中序遍历是有序的
遍历过程中，相邻元素进行比较，把出现频率高的元素输出
可以使用前后双指针pre和cur对树进行操作。
而且初始化pre = NULL从第一个元素开始比较
maxCount和上一个最大频率相等，result.push_back放进结果集,如果大于上一个，result.clear清空结果集，前面的都清除，把这个再push_back()，
class Solution{
private:
int maxCount = 0;
TreeNode* pre = NULL;
vector<int>result;
void searchBST(TreeNode* cur){
if(cur == NULL)return;
searchBST(cur->left);
if(pre == NULL){
count = 1;
}else if(pre->val == cur->val){
count++;
}else{
count = 1;
}
pre = cur;
if(count == maxCount){
result.push_back(cur->val);
}
if(count > maxCount){
maxCount = count;
result.clear();//清空result
result.push_back(cur->val);
}
searchBST(cur->right);
return;
}
public:
vector<int>findMode(TreeNode* root){
count = 0;
maxCount = 0;
pre = NULL;
result.clear();
searchBST(root);
return result;
}
};迭代法，把中序转成迭代，中间节点的处理逻辑完全一样。
class Solution{
public:
vector<int>findMode(TreeNode* root){
stack<TreeNode*>st;
TreeNode* cur = root;
TreeNode* pre = NULL;
int maxCount = 0;//最大频率
int count = 0;//统计频率
vector<int>result;
while(cur != NULL || !st.empty()){
if(cur != NULL){ //指针来访问节点，访问到最底层
st.push(cur);//将访问的节点放进栈
cur = cur->left;
}else{
cur = st.top();
st.pop(); //中
if(pre == NULL){//第一个节点
count = 1;
}else if(pre->val == cur->val){//与前一个节点数值相同
count++;
}else{//与前一个节点不同
count = 1;
}
if(count == maxCount){//如果和最大值相同，放进result
result.push_back(cur->val);
}
if(count > maxCount){//如果计数大于最大值频率
maxCount = count;//更新最大频率
result.clear();//清空result,让之前result里的元素失效
result.push_back(cur->val);
}
pre = cur;
cur = cur->right;//右
}
}
return result;
}
};二叉树的最近公共祖先
思路：一种情况是，该节点的左子树出现节点p，右子树出现节点q。另一种，节点p即为节点p和节点q的最近公共祖先。
二叉树节点数值是不重复的，所以p和q一定存在。节点本身p(q),它拥有一个子孙节点q(p).
第一种情况实现，顺带实现了情况二。
递归三部曲：
>>确定递归函数返回值及参数。
需要递归函数返回值，来告诉我们是否找到节点q或者p,那么返回值为bool类型就可以了。
但我们还要返回最近公共节点，可以利用上题目中返回值是TreeNode* ,那么如果遇到p或者q,就把q或者p返回，返回值不为空，就说明找到了q或者p.
TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* p,TreeNode* q)>>确定终止条件
遇到空的话，因为树是空的了，所以返回空。遇到q,p,将其返回。这个返回值，后面在中节点的处理过程中会用到。
if(root == q || root == p || root == NULL)return root;>>确定单层递归
值得注意的是，本题函数有返回值，是因为回溯的过程需要递归函数的返回值做判断，但本题我们依然要遍历树的所有节点。
在递归函数有返回值的情况下，如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left,right接住返回值，这个left,right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑(也就是回溯)。
搜索一条边：
if(递归函数(root->left))return ;
if(递归函数(root->right)) return ;
搜索整个树的写法：
left = 递归函数(root->left);//左
right = 递归函数(root->right);//右
left与right的逻辑处理；//中
用left和right接住左子树和右子树的返回值，代码如下：
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
如果left和right都不为空，说明此时root就是最近公共节点
如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之亦然。
if(left == NULL && right != NULL)return right;
else if (left != NULL && right == NULL)return left;
else {//left == NULL && right == NULL
return NULL;
}
class Solution{
public:
TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* p,TreeNode* q){
if(root == q || root == p || root == NULL)return root;
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
if(left != NULL && right != NULL)return root;
if(left == NULL && right != NULL)return right;
else if(left != NULL && right == NULL)return left;
else{//left == NULL && right == NULL
return NULL;
}
}
};精简后：
class Solution{
public:
TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* p,TreeNode* q){
if(root == q || root == p || root == NULL)return root;
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
if(left != NULL && right != NULL)return root;
if(left == NULL)return right;
return left;
}
};求最小公共祖先，需要从底层往上遍历，那么二叉树，只能通过后序遍历，实现从底向上的遍历方式。
在回溯过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值，也就是代码中国的left和right做逻辑判断。
要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。
可以说这里每一步，都是有难度的，都需要对二叉树，递归和回溯有一定的理解。
