1. 知识点总结

题目	难度	知识点
验证搜索二叉树	🐸	二叉树遍历
恢复二叉搜索树	🐸🐸🐸	morris遍历

2. 分题题解

2.1 验证搜索二叉树

简单题，但是好像不可以在遍历的时候做判断？所以开了数组

中序遍历解法：

class Solution {
public:
    vector<int>ans;
    void inTravel(TreeNode* root){
        if(root==NULL){
            return ;
        }else{
            inTravel(root->left);
            ans.push_back(root->val);
            inTravel(root->right);
        }
    }
    bool isValidBST(TreeNode* root) {
        inTravel(root);
        for(int i=0;i<ans.size();i++){
            if(i&&ans[i]<=ans[i-1]){
                return false;
            }
        }
        return true;
    }
};

参考官方题解后的递推解法：

class Solution {
public:
    vector<int>ans;
    bool F(TreeNode* root,long long higher,long long  lower){
        if(root==NULL){
            return true;
        }else if(root->val<=lower||root->val>=higher){
            //cout<<root->val<<" "<<lower<<" "<<higher<<"\n";
            return false;
        }else{
            return F(root->left,root->val,lower)&&F(root->right,higher,root->val);
        }
    }
    bool isValidBST(TreeNode* root) {
        return F(root,LONG_MAX,LONG_MIN);
    }
};

这样是不是舒服多啦😜

2.2 恢复二叉搜索树

答案写出来是不难，关键是空间复杂度如何降至O(1)

感觉像是自己默写了一遍题解，不是很理解，需要回炉

官方题解给了morris解法，看上去像是线索二叉树的中序遍历

/**
 * 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:
    TreeNode* a=NULL;
    TreeNode* b=NULL;
    TreeNode* pred=NULL;
    TreeNode* preprocessor=NULL;
    void recoverTree(TreeNode* root) {
        while(root!=NULL){
            //如果当前节点左孩子不为空
            if(root->left!=NULL){
                preprocessor=root->left;
                //找到左孩子的最右节点
                while(preprocessor->right!=NULL&&preprocessor->right!=root){
                    preprocessor=preprocessor->right;
                }
                if(preprocessor->right==NULL){
                    preprocessor->right=root;
                    root=root->left;
                }else{
                //说明左子树访问完毕:需要断开链接
                    if(pred!=NULL&&root->val<pred->val){
                        b=root;
                        if(a==NULL){
                            a=pred;
                        }
                    }
                    pred=root;
                    preprocessor->right=NULL;
                    root=root->right;
                    
                }
            }else{
                //如果没有左孩子，直接访问右孩子
                if(pred!=NULL&&root->val<pred->val){
                    b=root;
                    if(a==NULL){
                        a=pred;
                    }
                }
                pred=root;
                root=root->right;
                
            }
        }
        swap(a->val,b->val);
    }
};