ValidateBinarySearchTree的示例分析

小编给大家分享一下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的示例分析”有了一定的了解,如果想了解更多相关知识,欢迎关注创新互联行业资讯频道,感谢各位的阅读!


当前标题:ValidateBinarySearchTree的示例分析
网站地址:http://myzitong.com/article/jishcg.html