目錄

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

問題描述：

實現代碼與解析：

遞歸：

原理思路：

迭代（中序）：

思路原理：

---

問題描述：

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

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

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

示例 1：

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

示例 2：

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

實現代碼與解析： 遞歸：

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

原理思路：

? 根據二叉搜索樹的性質，我們中序遍歷轉化出來的數組一定是單調遞增的且沒有重復元素，代碼是很好寫出的。

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

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

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

class Solution {
public:
    TreeNode* pre = NULL; // 用來記錄前一個節點
    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; //記錄前一個結點
        bool right = isValidBST(root->right);
        return left && right;
    }
};

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

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

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

迭代（中序）：

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;//保存結點
                root=root->right;
            }
        }
        return true;
    }
};

思路原理：

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

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

文章題目：Leetcode：98.驗證二叉搜索樹（C++）-創新互聯
轉載源于：http://vcdvsql.cn/article14/icgge.html

成都網站建設公司_創新互聯，為您提供服務器托管、用戶體驗、商城網站、網站導航、自適應網站、微信公眾號

廣告

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