==42==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000298 at pc 0x00000034c00c bp 0x7ffe79bf4ca0 sp 0x7ffe79bf4c98
1

这种错误我想刷力扣的同学应该都没少遇到过，这个一般最常见的意思就是你设置的数据访问越界了，但是对于边界的设置很多时候我们已经很注意了，为什么还是会出现这类的问题呢？
今天的练习过程中，我意识到了一个我之前确实经常忽视的问题，在此进行分享。

这里就先直接说了吧，具体的案例可以看下面的，就是我们在进行条件判定的时候，经常是条件1&&条件2，但是这样的类型就需要我们注意边界判定要在前面，具体情况的数值的判定在后面，不然的话就会先计算数据条件，这个时候就会出现越界的问题，虽然我们设置了边界判定，但是因为计算次序的原因，是用不上的。

题目：恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/recover-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的解题思路

这里的具体解题思路还算是比较明确的，毕竟就是叫我们修改一下树中的一些节点的数值嘛，找到有问题的两个节点，把数值对调就可以了。

那如何找这两个点呢？我们首先需要进行一下中序遍历，既然只有两个点是错误的，那么我们可以直接遍历list，找到第一对不是单调不下降的数对，基于此，把第二个数继续往后遍历，直到这个数确实比第一个数大了，这时我们就找到了有问题的两个数了。

那么我们该怎么实现数据的对换呢？其实也就是遍历对数据，因为这种情况，有问题的两个数是必不可能在树中有相同数值的节点的，所以直接找，找到了就换另一个即可，这里递归一下即可。

最后说一下我第一次的bug问题，主要还是边界控制上，一定要把边界控制的条件放在前面，就像while(biao<=l-1&&list[i]>list[biao])这样，如果把这里的两个条件对调一下位置，就会出现越界报错，这确实是一个我知道，但是不曾注意过的一个问题。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> list;
    void inorder(TreeNode* root){
        if(root==nullptr){
            return;
        }
        else{
            inorder(root->left);
            list.push_back(root->val);
            inorder(root->right); 
        }
    }

    void recover(TreeNode* root,int count,int x,int y)
    {
        if(root!=nullptr){
            if(root->val==x||root->val==y){
                int nnum=root->val==x?y:x;
                root->val=nnum;
                count--;
                if(count==0){
                    return;
                }     
            }     
            recover(root->left,count,x,y);
            recover(root->right,count,x,y);                  
            
        }

    }

    void recoverTree(TreeNode* root) {
        inorder(root);
        int l=list.size();
        for(int i=0;i<l;i++){
            cout<<list[i]<<" ";
        }
        cout<<endl;
        for(int i=0;i<l-1;i++){
            if(list[i]>list[i+1]){
                cout<<l<<endl;
                int biao=i+1;
                while(biao<=l-1&&list[i]>list[biao]){
                    biao++;
                }
                biao--;
                cout<<list[i]<<" "<<list[biao]<<endl;
                recover(root,2,list[i],list[biao]);
                break;
            }
        }
        return;
    }
};
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

ps：这个就是本人的代码