目錄

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

問題描述：

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

遞歸：

原理思路：

迭代（中序）：

思路原理：

---

問題描述：

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

有效?二叉搜索樹定義如下：

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

示例 1：

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

示例 2：

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

實現(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ù)二叉搜索樹的性質(zhì)，我們中序遍歷轉(zhuǎn)化出來的數(shù)組一定是單調(diào)遞增的且沒有重復(fù)元素，代碼是很好寫出的。

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

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

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

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

? 其實第一次看這個題，我想的是比較左右子樹與根結(jié)點的值大小來判斷返回，就像這樣：

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

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

迭代（中序）：

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é)點
                root=root->right;
            }
        }
        return true;
    }
};

思路原理：

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

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

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

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

廣告

聲明：本網(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)