歡迎訪問我的GitHub

這里分類和匯總了欣宸的全部原創(chuàng)(含配套源碼)：https://github.com/zq2599/blog_demos

關于LeetCode98

• 做這道題之前，我反復審題，最后確認：沒錯，不存在什么坑，這道題確實非常非常簡單，然而卻被官方定義為中等難度
• 這一定是送分，白撿一道中等難度題，接下來，一起來輕松愉快的享受解題過程吧

關于題目

• 題目：98. 驗證二叉搜索樹
• 描述

給你一個二叉樹的根節(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 。

• 提示：

樹中節(jié)點數(shù)目范圍在[1, 104] 內
-231 <= Node.val <= 231 - 1

分析

• 簡單的說，此題的要求如下圖所示：紅色節(jié)點的值都小于100，藍色節(jié)點的值都大于100，然后，往每個子節(jié)點上套這個規(guī)則即可
  
• 此題有兩處需要注意：

1. 對于任意節(jié)點，它的左子樹都要小于節(jié)點值，右子樹必須大于節(jié)點值，不允許等于，一旦出現(xiàn)就返回false
2. 節(jié)點值的范圍：下限是int的最小值，上限是int的最大值

• 只要注意以上兩點，就能憑借最基礎的二叉樹遍歷基本功解題了

解題思路

• 還是以下圖來說明
  
• 上圖中，不論紅色還是藍色節(jié)點，都可以設置好一個范圍區(qū)間，然后檢查這些節(jié)點在不在區(qū)間內，這就是解題思路
• 其實就是中規(guī)中矩的前序遍歷（口訣：根左右），每個節(jié)點都是先檢查自己在不在規(guī)定范圍內，然后再處理其左子樹和右子樹，在處理的時候，要重新設定范圍，對左子樹，要更新上限，對右子樹，要更新下限
• 上圖中，對紅色節(jié)點的要求是小于100，也就是說上限是100，至于下限？無所謂，那就用int的最小值-2147483648作為下限？
• 絕對不行！??！因為：節(jié)點值可能就是int的最小值！
• 同理，處理藍色節(jié)點的時候，也不能用int型的最大值2147483647作為上限
• 要用long型的最小值作為紅色的下限，long型的最大值作為上限
• 分析完成，接下來開始編碼

編碼

• 完整代碼如下，唯一要注意的就是默認上限是Long.MAX_VALUE，默認下限是Long.MIN_VALUE：

class Solution {
    public boolean isValidBST(TreeNode root) {

        // 左子樹，只要求不能比自己大，至于小到什么程度都無所謂，所以用int最小值作為左側邊界
        if (!isValidBST(root.left, Long.MIN_VALUE, root.val)) {
            return false;
        }

        // 右子樹，只要求不能比自己小，至于達到什么程度都無所謂，所以用int最大值作為右側邊界
        if (!isValidBST(root.right, root.val, Long.MAX_VALUE)) {
            return false;
        }

        return true;
    }

    public boolean isValidBST(TreeNode root, long min, long max) {
        if (null==root) {
            return true;
        }

        // 檢查自己
        // 注意審題：左側必須比自己小，不接受等于，右側必須必自己大，不接受等于
        if (root.val<=min || root.val>=max) {
            return false;
        }

        // 左子樹，只要求不能比自己大，至于小到什么程度都無所謂，所以用入?yún)⒌淖钚≈底鳛樽髠冗吔?        if (!isValidBST(root.left, min, Math.min(max, root.val))) {
            return false;
        }

        // 右子樹，只要求不能比自己小，至于達到什么程度都無所謂，所以用入?yún)⒌淖畲笾底鳛橛覀冗吔?        if (!isValidBST(root.right, Math.max(min, root.val), max)) {
            return false;
        }

        return true;
    }
}

• 提交，順利AC，用時擊敗100%
  
• 至此，解題完成，至今也沒弄明白，一個二叉樹遍歷基本功考核，怎么就成了中級難度

歡迎關注博客園：程序員欣宸

學習路上，你不孤單，欣宸原創(chuàng)一路相伴...文章來源地址http://www.zghlxwxcb.cn/news/detail-707521.html

到了這里，關于LeetCode98：驗證二叉搜索樹，居然有這么簡單的中等難度，白撿(用時擊敗100%)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！