13518219792
小编给大家分享一下Validate Binary Search Tree的示例分析，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！
成都创新互联专业为企业提供深州网站建设、深州做网站、深州网站设计、深州网站制作等企业网站建设、网页设计与制作、深州企业网站模板建站服务，10余年深州做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
解法一：
递归思想，递归先序遍历，假定当前结点为root,其左子树右下角节点为pre,右子树左下角节点为next
情况一：root==NULL,return true
情况二：
root!=NULL,则判断，
a)如果有左孩子，则如果root->left->val>=root->val ,则返回false；
b）如果比左子树中右下角元素小，return false;
c)如果有右孩子，即如果root->right->val<=root->val,则返回false；
d)如果比右子树左下角大，即如果next->val<=root->val,return false;
如果a,b,c,d都不为真，则说明，当前节点值比左孩子大，且比其前序节点值大，比右孩子小，且比后续节点值小，这时返回左子树和右子树的结果。
即
最后return BST(root->left)&&BST(root->right)
TreeNode* findpre(TreeNode *root){
if(!root||!root->left)
return NULL;
TreeNode *p=root->left;
while(p->right){
p=p->right;
}
return p;
}
TreeNode* findnext(TreeNode *root){
if(!root||!root->right)
return NULL;
TreeNode *p=root->right;
while(p->left){
p=p->left;
}
return p;
}
bool isValidBST(TreeNode* root) {
if(!root)
return true;
if(root->left&&root->left->val>=root->val)
return false;
if(root->right&&root->right->val<=root->val)
return false;
TreeNode *pre=findpre(root),*next=findnext(root);
if(pre&&pre->val>=root->val||next&&next->val<=root->val)
return false;
return isValidBST(root->left)&&isValidBST(root->right);
}解法二：
从解法一看出，其实只要保证，当前值比左子树pre节点大，且比右子树next节点值小即可，可以把a,b,这两种情况注释掉，但存在也是有一定用处的，可以首先判断左右孩子，如果左右孩子都不满足，则就不用找前序和后继了。
bool isValidBST(TreeNode* root) {
if(!root)
return true;
/*if(root->left&&root->left->val>=root->val)
return false;
if(root->right&&root->right->val<=root->val)
return false;*/
TreeNode *pre=findpre(root),*next=findnext(root);
if(pre&&pre->val>=root->val||next&&next->val<=root->val)
return false;
return isValidBST(root->left)&&isValidBST(root->right);
}解法三：
其实，利用中序遍历可以得到有序序列，只要当前节点比前一个节点大，即是BST，
bool isValidBSTCore(TreeNode *root,TreeNode *&pre){
if(!root)
return true;
if(!isValidBSTCore(root->left,pre))//左子树
return false;
if(pre&&pre->val>=root->val)//当前结点与前节点比较
return false;
pre=root;//修改pre
return isValidBSTCore(root->right,pre);//右子树
}
bool isValidBST(TreeNode* root) {
if(!root)
return true;
TreeNode *pre=NULL;
return isValidBSTCore(root,pre);
}看完了这篇文章，相信你对“Validate Binary Search Tree的示例分析”有了一定的了解，如果想了解更多相关知识，欢迎关注创新互联行业资讯频道，感谢各位的阅读！
