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

I think this kind of mistake should have been encountered by students who brush force buttons , This usually means that the data access you set is out of bounds , But we have paid much attention to the setting of the boundary many times , Why are there still such problems ？
During today's practice , I realized a problem that I really often ignored before , Share here .

Let's just say it directly here , Specific cases can be seen in the following , It's when we make a condition determination , Often a condition 1&& Conditions 2, But for this type, we need to pay attention to the boundary determination in front , The determination of the specific value is later , Otherwise, the data conditions will be calculated first , At this time, there will be cross-border problems , Although we set up boundary determination , But because of the order of calculation , It's useless .

subject ： Restore binary search tree

Give you the root node of the binary search tree root , In the tree just The values of the two nodes are incorrectly exchanged . Please... Without changing its structure , Restore the tree .
Input ：root = [1,3,null,null,2]
Output ：[3,1,null,null,2]
explain ：3 It can't be 1 The left child , because 3 > 1 . In exchange for 1 and 3 Make the binary search tree efficient .

Input ：root = [3,1,4,null,null,2]
Output ：[2,1,4,null,null,3]
explain ：2 Can't be in 3 In the right subtree , because 2 < 3 . In exchange for 2 and 3 Make the binary search tree efficient .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/recover-binary-search-tree
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

My solution to the problem

The specific solution idea here is relatively clear , After all, let's modify the values of some nodes in the tree , Find the two nodes with problems , Just switch the values .

How to find these two points ？ First, we need to traverse the middle order , Since only two points are wrong , Then we can directly traverse list, Find the first pair that is not monotonous and does not decline , Based on this , Continue traversing the second number back , Until this number is indeed larger than the first number , Then we found the two numbers in question .

So how do we realize data exchange ？ In fact, it means traversing the data , Because of this situation , It is impossible for the two numbers in question to have nodes with the same value in the tree , So go straight to , If you find it, just change to another one , Just recurse here .

Finally, let's talk about my first bug problem , It's mainly about border control , We must put the conditions of boundary control in front , It's like while(biao<=l-1&&list[i]>list[biao]) such , If the two conditions here are reversed , There will be cross-border error reporting , This is really a I know , But I haven't noticed a problem .

/** * 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;
    }
};

ps： This is my code