目錄

創(chuàng)新互聯(lián)是一家成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站，提供網(wǎng)頁(yè)設(shè)計(jì)，網(wǎng)站設(shè)計(jì)，網(wǎng)站制作，建網(wǎng)站，按需網(wǎng)站制作，網(wǎng)站開(kāi)發(fā)公司，于2013年創(chuàng)立是互聯(lián)行業(yè)建設(shè)者，服務(wù)者。以提升客戶品牌價(jià)值為核心業(yè)務(wù)，全程參與項(xiàng)目的網(wǎng)站策劃設(shè)計(jì)制作，前端開(kāi)發(fā)，后臺(tái)程序制作以及后期項(xiàng)目運(yùn)營(yíng)并提出專業(yè)建議和思路。

問(wèn)題描述：

實(shí)現(xiàn)代碼與解析：

遞歸：

原理思路：

迭代（中序）：

思路原理：

---

問(wèn)題描述：

給你一個(gè)二叉樹(shù)的根節(jié)點(diǎn)?root，判斷其是否是一個(gè)有效的二叉搜索樹(shù)。

有效?二叉搜索樹(shù)定義如下：

• 節(jié)點(diǎn)的左子樹(shù)只包含?小于?當(dāng)前節(jié)點(diǎn)的數(shù)。
• 節(jié)點(diǎn)的右子樹(shù)只包含?大于?當(dāng)前節(jié)點(diǎn)的數(shù)。
• 所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)。

示例 1：

輸入：root = [2,1,3]
輸出：true

示例 2：

輸入：root = [5,1,4,null,null,3,6]
輸出：false
解釋：根節(jié)點(diǎn)的值是 5 ，但是右子節(jié)點(diǎn)的值是 4 。

實(shí)現(xiàn)代碼與解析： 遞歸：

class Solution {
public:
    void traversal(TreeNode* root,vector& vec)
    {
        if(root==NULL) return;
        traversal(root->left,vec);
        vec.push_back(root->val);//中序
        traversal(root->right,vec);

    }
    bool isValidBST(TreeNode* root) 
    {
        vectorvec;
        traversal(root,vec);
        for(int i=1;i=vec[i]) return false; 
        }
        return true;
    }
};

原理思路：

? 根據(jù)二叉搜索樹(shù)的性質(zhì)，我們中序遍歷轉(zhuǎn)化出來(lái)的數(shù)組一定是單調(diào)遞增的且沒(méi)有重復(fù)元素，代碼是很好寫(xiě)出的。

? 當(dāng)然也可以不用數(shù)組，直接在遞歸時(shí)判斷出來(lái)是否有序。下面給出代碼：

class Solution {
public:
    long max=LONG_MIN;
    bool isValidBST(TreeNode* root) 
    {
       if(root==NULL) return true;
       bool left=isValidBST(root->left);
       if(root->val>max) max=root->val;//更新大值
       else return false;//若不遞增，不用再向右遍歷了直接返回false
       bool right=isValidBST(root->right);
       return left&&right;
    }
};

? 這題測(cè)試數(shù)據(jù)中有INT_MIN，所以這里我們用LONG_MIN，當(dāng)然如果這里測(cè)試數(shù)據(jù)有最小的LLONG_MIN，無(wú)法找出比它還小的值，那我們就換一種方式來(lái)比較，記錄前一個(gè)結(jié)點(diǎn)值來(lái)判斷即可：

class Solution {
public:
    TreeNode* pre = NULL; // 用來(lái)記錄前一個(gè)節(jié)點(diǎn)
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);
        //當(dāng)pre不為空
        if (pre != NULL && pre->val >= root->val) return false;
        pre = root; //記錄前一個(gè)結(jié)點(diǎn)
        bool right = isValidBST(root->right);
        return left && right;
    }
};

? 其實(shí)第一次看這個(gè)題，我想的是比較左右子樹(shù)與根結(jié)點(diǎn)的值大小來(lái)判斷返回，就像這樣：

if(root->val<=root->left->val||root->val>=root->right->val) return false;

后來(lái)發(fā)現(xiàn)，其實(shí)這樣是錯(cuò)誤的，這樣只判斷左右子樹(shù)的根節(jié)點(diǎn)，而二叉搜索樹(shù)是左子樹(shù)所有結(jié)點(diǎn)都小于根結(jié)點(diǎn)，右子樹(shù)的所有結(jié)點(diǎn)都大于根節(jié)點(diǎn)，所以不能這樣寫(xiě)。

迭代（中序）：

class Solution {
public:
    bool isValidBST(TreeNode* root) 
    {
        stackst;
        TreeNode* pre=NULL;
        while(root!=NULL||!st.empty())
        {
            if(root!=NULL)
            {
                st.push(root);
                root=root->left;
            }
            else
            {
                root=st.top();
                st.pop();
                if(pre!=NULL&&root->val<=pre->val) return false;
                pre=root;//保存結(jié)點(diǎn)
                root=root->right;
            }
        }
        return true;
    }
};

思路原理：

? 在中序遍歷的代碼上做一定修改即可。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章題目：Leetcode：98.驗(yàn)證二叉搜索樹(shù)（C++）-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://www.rwnh.cn/article14/icgge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供服務(wù)器托管、用戶體驗(yàn)、商城網(wǎng)站、網(wǎng)站導(dǎo)航、自適應(yīng)網(wǎng)站、微信公眾號(hào)

廣告

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