Leetcode 98. Validate Binary Search Tree

給定二叉樹的根，確定它是否是有效的二叉搜索樹 (BST)。有效的 BST 定義如下：

root的左子樹小於root的節點。
root的右子樹大於root的節點。
左右子樹也必須是二叉搜索樹。

Python

方法一 : In-order Traversal

In-order的順序為左-中-右，代表每次先拿到左邊的值，接著是中間，最後才是右邊值，已經知道在In-order的狀況下，對於二元搜尋樹可以得到一個由小到大的順序，判斷 list 中的值如果是遞增的順序那麼說明是有效的BST，當現在的節點小於或相等於上一個節點時，表示這不是二元搜尋樹

class Solution(object):
    def isValidBST(self, root):
        l=[]
        def dfs(root):
            if not root:
                return
            dfs(root.left)      #先左邊
            l.append(root.val)  #root的值
            dfs(root.right)     #再右邊
        dfs(root)
        for i in range(1,len(l)):
            if l[i]<=l[i-1]:   #現在的節點小於或相等於上一個節點
                return False   #不是二元搜尋樹
        return True

方法二 : 遞歸

class Solution(object):
    def isValidBST(self, root):
        return self.valid(root,float("-inf"),float("inf"))
    def valid(self,root,min,max):
        if not root : return True
        if root.val>=max or root.val<=min:  # root大於右子 樹 或 root小於左子樹 
            return False
        return self.valid(root.left,min,root.val) and self.valid(root.right,root.val,max)

C++

方法一 : 遞歸

利用二叉搜索樹的性質，對於二叉搜索樹中的任意節點，它的左子樹中的所有節點的值都比它小，它的右子樹中的所有節點的值都比它大。對於每個節點，我們都需要給定一個上下界，來限制該節點的值是否在合法的範圍內。在遞歸的過程中，我們首先判斷當前節點是否為空，如果為空則返回 true。然後判斷當前節點的值是否在給定的上下界之間，如果不是則返回 false。最後分別遞歸判斷當前節點的左子樹和右子樹，其中左子樹的上界為當前節點的值，右子樹的下界為當前節點的值。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isBST(root, LONG_MIN, LONG_MAX);
    }
private:
    bool isBST(TreeNode* root, long long minVal, long long maxVal) {
        if (!root) return true;
        if (root->val <= minVal || root->val >= maxVal) return false;
        return isBST(root->left, minVal, root->val) && isBST(root->right, root->val, maxVal);
    }
};

方法二 : 棧

中序遍歷的順序是左子樹 – 根節點 – 右子樹，對於二叉搜索樹來說，中序遍歷的結果一定是一個升序序列。因此，我們可以使用一個指針 prev 來記錄上一個中序遍歷的節點，然後依次遍歷每個節點，判斷該節點的值是否大於 prev 的值即可。具體的實現方法是，使用一個棧來模擬中序遍歷的過程，對於當前節點，先將其所有左子節點都入棧，然後取出棧頂節點，如果該節點的值小於等於 prev 的值，說明該二叉搜索樹不合法，直接返回 false。否則，更新 prev 的值，並將當前節點的右子節點入棧。需要注意的是，由於 prev 的初始值為 nullptr，因此我們需要在第一次遍歷時特判一下，直接將當前節點賦值給 prev。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode* prev = nullptr;
        while (root || !s.empty()) {
            while (root) {
                s.push(root);
                root = root->left;
            }
            root = s.top();
            s.pop();
            if (prev && root->val <= prev->val) return false;
            prev = root;
            root = root->right;
        }
        return true;
    }
};

Python

C++

相關