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

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

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);
}
};