二叉树abcdefghij先序遍历_二叉搜索树的查找递归算法

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

题解
深搜

/** * 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:
    const int INF = 0x3f3f3f3f;
    const int OINF = -0x3f3f3f3f;
    bool dfs(TreeNode * t,int &Min,int &Max){ 
   
        if(t->left == NULL && t->right == NULL){ 
   
            Min = t->val,Max = t->val;
            return true;
        }
        int tlMax = t->val,tlMin = t->val,trMax = t->val,trMin = t->val;
        Min = Max = t->val;
        if(t->left){ 
   
            if(!dfs(t->left,tlMin,tlMax))return false;
            else{ 
   
                if(tlMax >= t->val || tlMin >= t->val)return false;
                Min = min(tlMin,Min);
                Max = max(tlMax,Max);
            }
        }
        if(t->right){ 
   
            if(!dfs(t->right,trMin,trMax))return false;
            else{ 
   
                if(trMax <= t->val || trMin <= t->val)return false;
                Min = min(trMin,Min);
                Max = max(trMax,Max);
            }
        }
        return true;
    }
    bool isValidBST(TreeNode* root) { 
   
        int a = 0,b = 0;
        return dfs(root,a,b);
    }
};

2. 仍然为深搜
   dfs(root,lower,upper):代表以root为根节点的树是否在lower和upper范围内

/** * 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:
    const long long INF = 0x3f3f3f3f3f3f3f3f;
    bool dfs(TreeNode *root,long long lower,long long upper){ 
   
        if(root->left == NULL && root->right == NULL){ 
   
            if(root->val > lower && root->val < upper)return true;
            else return false;
        }
        if(root->val <= lower || root->val >= upper)return false;
        if(root->left && !dfs(root->left,lower,root->val))return false;
        if(root->right && !dfs(root->right,root->val,upper))return false;

        return true;
    }
    bool isValidBST(TreeNode* root) { 
   
        cout<<INF<<endl;
        return dfs(root,-INF,INF);
    }
};

3. 中序遍历

/** * 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>res;
    bool dfs(TreeNode *root){ 
   
        if(root == NULL)return true;
        if(!dfs(root->left))return false;
        res.push_back(root->val);
        if(res.size() >= 2 && res[res.size() - 1] <= res[res.size() - 2])return false;
        if(!dfs(root->right))return false;

        return true;
    }
    bool isValidBST(TreeNode* root) { 
   
        return dfs(root);
    }
};