小編給大家分享一下Validate Binary Search Tree的示例分析，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

成都創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供深州網(wǎng)站建設(shè)、深州做網(wǎng)站、深州網(wǎng)站設(shè)計、深州網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計與制作、深州企業(yè)網(wǎng)站模板建站服務(wù)，10余年深州做網(wǎng)站經(jīng)驗，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡(luò)服務(wù)。

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.

解法一：

遞歸思想，遞歸先序遍歷，假定當(dāng)前結(jié)點為root,其左子樹右下角節(jié)點為pre,右子樹左下角節(jié)點為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都不為真，則說明，當(dāng)前節(jié)點值比左孩子大，且比其前序節(jié)點值大，比右孩子小，且比后續(xù)節(jié)點值小，這時返回左子樹和右子樹的結(jié)果。

即

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

解法二：

從解法一看出，其實只要保證，當(dāng)前值比左子樹pre節(jié)點大，且比右子樹next節(jié)點值小即可，可以把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);
    }

解法三：

其實，利用中序遍歷可以得到有序序列，只要當(dāng)前節(jié)點比前一個節(jié)點大，即是BST，

bool isValidBSTCore(TreeNode *root,TreeNode *&pre){
        if(!root)
            return true;
        if(!isValidBSTCore(root->left,pre))//左子樹
            return false;
        if(pre&&pre->val>=root->val)//當(dāng)前結(jié)點與前節(jié)點比較
            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的示例分析”有了一定的了解，如果想了解更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

網(wǎng)頁題目：ValidateBinarySearchTree的示例分析
當(dāng)前路徑：http://www.rwnh.cn/article26/jishcg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、網(wǎng)站策劃、App設(shè)計、品牌網(wǎng)站建設(shè)、建站公司、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)