代码随想录 | Day23 | 二叉树：二叉搜索树的最小绝对差&&二叉搜索树中的众数

主要学习内容：

1.二叉搜索树性质：中序遍历是递增的有序序列

2.自定义pair排序函数复习

3.双指针在二叉树中的应用（重点）

530.二叉搜索树的最小绝对差

530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

解法：利用二叉搜索树性质进行中序遍历

**思路：**总的思路是二叉搜索树的中序遍历是一个递增的有序序列，可以把它看成一个数组。

那么就有了两个思路

1.把遍历的数全都存到一个数组中，然后循环，看相邻两个数的差的大小，记录最小值就是了

2.在遍历的过程中想办法把前一个结点的值给记下来，然后根据遍历顺序进行相减得到最后的结果。可以利用双指针来记录前一个节点

在这里介绍第二种

1.函数参数和返回值

1
2
3
int minVal=INT_MAX;
TreeNode *pre=nullptr;
void tra(TreeNode *t)

minVal记录答案

pre是慢指针，指向前一个遍历的结点，用来和当前结点t进行相减操作，慢指针初始化为空是因为我们并不知道有序序列第一个结点是哪个

本题无需返回值

2.终止条件

1
2
if(t==nullptr)
	return;

遇到空直接返回

3.本层代码逻辑

中序遍历。

需要注意的是慢指针的更新操作。

有两种情况，当我们没有找到有序序列第一个数时慢指针是空的，我们只有找到第一个数之后才能把慢指针更新，之后才能进行minVal的更新。

快慢指针的更新操作要在左中右的中，即本层。

1
2
3
4
5
6
7
8
9
10
11
tra(t->left);//左
//中
if(pre!=nullptr)
{
    //更新minval，即快指针减去慢指针的值
	if(t->val-pre->val<minVal)
	minVal=t->val-pre->val;
}
pre=t;//更新慢指针
//右
tra(t->right);

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minVal=INT_MAX;
    TreeNode *pre=nullptr;
    void tra(TreeNode *t)
    {   
        if(t==nullptr)
            return;
        tra(t->left);
        if(pre!=nullptr)
        {
            if(t->val-pre->val<minVal)
                minVal=t->val-pre->val;
        }
        pre=t;
        tra(t->right);
    }
    int getMinimumDifference(TreeNode* root) {
        tra(root);
        return minVal;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//直接遍历代码
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;
    }
};

难点：1.想到用双指针记录

2.慢指针的更新操作

本次犯的错误：

想着记录minval时直接把两个数相减，但其实连t->val和val的前后关系都没弄对，传入根结点时，也不会知道前面的第一个结点的值到底是多少，最后也自然得不到结果，直接传值也没法像慢指针那样有nullptr作为标志，因为你设置的标志值可能就是第一个结点的值。

比如说

1
2
3
4
5
6
if(val!=0)
{
    更新minval
}
val=t->val;
但是0可能就是我们找的第一个结点的值。
1
2
3
4
5
6
7
8
9
10
11
错误示范：
	int minVal=INT_MAX;
    void tra(TreeNode *t,int val)
    {
        if(t==nullptr)
            return;
        tra(t->left,t->val);
        if(val-t->val<minVal)
            minVal=val-t->val;
        tra(t->right,t->val);
    }

501.二叉搜索树中的众数

501. 二叉搜索树中的众数 - 力扣（LeetCode）

解法：直接遍历

思路1：

直接想法：遍历得到一个有序数组然后通过map进行统计出现频率，key记录出现的值，value记录出现频率，再把map转化为vector进行排序，所以也需要自定义一个关于pair<int,int>的排序算法。这种适合所有的二叉树找众数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    map<int,int> p;
    //随便一种遍历方式就行
    void tra(TreeNode *t)
    {
        if(t==nullptr)  
            return ;
        p[t->val]++;
        tra(t->left);
        tra(t->right);
    }
    //map转vector排序函数
    bool static cmp(pair<int,int> a,pair<int,int> b)
    {
        return a.second>b.second;
    }
    vector<int> findMode(TreeNode* root) {
        tra(root);
        //map转vector
        vector<pair<int,int>> v(p.begin(),p.end());
        //排序
        sort(v.begin(),v.end(),cmp);
        vector<int> res;
        res.push_back(v[0].first);
        //记录相同频率众数
        for(int i=1;i<v.size();i++)
        {
            if(v[i].second==v[0].second)
                res.push_back(v[i].first);
            else
                return res;
        }
        return res;
    }
};
思路2：

中序遍历，这个比较难想到但是比较好理解。

首先我们只知道二叉搜索树中序遍历可以得到有序序列，两个一样的数必然是相邻的，这样统计频率就很好统计，我们只需要设置一个计数器表示这个数字的频率，前后一样的话就把计数器++。

问题是，我们要怎么设置这个计数器，在遍历的同时可以记录频率，又如何来判断前后两个数是否相同

首先，判断两个数是否相同，我们可以用上一道题的双指针，建立一个快慢指针，两个指针一前一后，判断两个数是否相同，相同的话就把计数器++。

现在来回答如何建立计数器的问题，我们需要两个全局变量

1
2
3
4
5
int maxcount=-1;//记录当前遍历过的最大频率的数的频率
int count=1;//记录当前正在遍历的数的频率

TreeNode *pre=nullptr;//慢指针
void tra(TreeNode *t)//传递的t是快指针

我们先来解决当前结点的数的频率记录问题，再去想全部的结点的频率记录问题

如果只对于一组快慢指针即只有两个结点，如果二者都不为空且数值一样，那么计数器是不是要++

如果慢指针为空，那说明慢指针还没有更新，还没有出现序列，频率自然就为1，和初始化一样

如果两者不为空数值不同，那说明当前结点的计数器还是1，不需要任何操作

我们把这段话实现一下

1
2
3
4
5
6
if(pre==nullptr)//还没有出现序列
	count=1;
else if(pre->val==t->val)//两个结点数值相同
	count++;
else    
	count=1;

现在来想如何把这两个结点的频率记录扩展到全部结点

没错，需要maxcount，maxcount记录当前结点的最大值，只有当前结点的count大于等于maxcount时我们才会把它放入我们的结果集res中

1
2
3
4
5
6
7
if(count==maxcount)
	res.push_back(t->val);
if(count>maxcount)
{
	maxcount=count;//更新maxcount
	res.push_back(t->val);
}

如果只是这样的话那这个不就太容易放入我们的结果集了吗？

所以我们每次更新maxcount要加入一个操作

1
res.clear();

即清空前面所有的结果集，注意这个是很重要的。而且在等于的时候我们并不会清除，只是会把答案放入其中。

1.函数参数和返回值

1
2
3
4
5
int maxcount=-1;//最大频率值
int count=1;//当前频率值
TreeNode *pre=nullptr;//慢指针
vector<int> res;//结果集
void tra(TreeNode *t)//快指针

2.终止条件

1
2
if(t==nullptr)
	return ;

3.本层代码逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//左
tra(t->left);
//中
      if(pre==nullptr)
          count=1;
      else if(pre->val==t->val)
          count++;
      else    
          count=1;
      pre=t;//慢指针更新，不要忘记
      if(count==maxcount)
          res.push_back(t->val);
      if(count>maxcount)
      {
          maxcount=count;
          res.clear();//清空结果集
          res.push_back(t->val);
      }
//右
      tra(t->right);

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int maxcount=-1;
    int count=1;
    TreeNode *pre=nullptr;
    vector<int> res;
    void tra(TreeNode *t)
    {
        if(t==nullptr)
            return ;
        tra(t->left);
        if(pre==nullptr)
            count=1;
        else if(pre->val==t->val)
            count++;
        else    
            count=1;
        pre=t;
        if(count==maxcount)
            res.push_back(t->val);
        if(count>maxcount)
        {
            maxcount=count;
            res.clear();
            res.push_back(t->val);
        }
        tra(t->right);
    }
    vector<int> findMode(TreeNode* root) {
        tra(root);
        return res;
    }
};

至此，只需要一遍遍历就把答案纪律完毕。

注：501需要及时复习