1. 題目

描述

給定一個二叉樹根節點，請你判斷這棵樹是不是二叉搜索樹。

二叉搜索樹滿足每個節點的左子樹上的所有節點的值均嚴格小于當前節點的值；并且右子樹上的所有節點的值均嚴格大于當前節點的值。

數據范圍：節點數量滿足 1≤n≤10^4^ ，節點上的值滿足 -2^31^ ≤val≤2^31^?1

示例1

輸入：

{1,2,3}

返回值：

false

示例2

輸入：

{2,1,3}

返回值：

true

2. 解題思路

先來看二叉搜索樹的性質：

二叉搜索樹（Binary Search Tree，簡稱BST）是一種特殊的二叉樹，其每個節點的值都大于其左子樹中所有節點的值并且小于其右子樹中所有節點的值。二叉搜索樹允許快速查詢、插入和刪除操作，多數操作（插入、刪除和查找）的時間復雜度都是O(log n)。

以下是二叉搜索樹的一些基本特性：

1.左子樹的所有節點的值都小于其父節點。

2.右子樹的所有節點的值都大于其父節點。

3.左、右子樹也必須是二叉搜索樹。

4.每個節點只有一個父節點（除了根節點）和最多兩個子節點（左子節點和右子節點）。

判斷一顆二叉樹是否為二叉搜索樹依賴于樹的左右子樹。可以采用遞歸的方法。

先來看看是否滿足遞歸的兩個條件：

可以看出，判斷二叉樹是否為二叉搜索樹的求解滿足遞歸的兩個條件，因此可以采用遞歸的方法進行求解。

一顆二叉樹是否為二叉搜索樹依賴于節點的左右子樹。對于左子樹，取值范圍為：（-∞，root.val]；對于右子樹，取值范圍為： [root.val,+∞)。因此對應的遞推公式如下：

有了遞推公式，就可以很方便的寫出對應的代碼。

如果文字描述的不太清楚，你可以參考視頻的詳細講解。

• Python版本：https://www.bilibili.com/cheese/play/ep1372111https://www.bilibili.com/cheese/play/ep1372111

• Java版本：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1367350

• Golang版本：數據結構筆試面試算法-Go語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Go語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1364775

3. 編碼實現

/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可*** @param root TreeNode類* @return bool布爾型*/
func isValidBST(root *TreeNode) bool {// write code herereturn recursion(root, math.MinInt32, math.MaxInt32) //對于二叉樹來說，取值范圍為：(-∞,+∞)
}func recursion(root *TreeNode, min int, max int) bool {// 2. 遞歸終止條件:// 2.2 如果二叉樹為空，是搜索二叉樹if root == nil {return true}// 2.2 如果當前節點的值小于min或者 大于max，則不是二叉搜索樹if root.Val < min || root.Val > max {return false}// 1. 問題分解（遞推公式）//左子樹取值范圍：(min,root.val]；	右子樹取值范圍：[root.val,max)return recursion(root.Left, min, root.Val) && recursion(root.Right, root.Val, max)
}

具體完整代碼你可以參考下面視頻的詳細講解。

• Python版本：https://www.bilibili.com/cheese/play/ep1372111https://www.bilibili.com/cheese/play/ep1372111

• Java版本：數據結構筆試面試算法-Java語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Java語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1367350

• Golang版本：https://www.bilibili.com/cheese/play/ep1364775https://www.bilibili.com/cheese/play/ep1364775

4.小結

判斷一顆二叉樹是否為二叉搜索樹依賴于樹的左右子樹。可以采用遞歸的方法。對于節點的左子樹，取值范圍為：（-∞，root.val]；對于節點的右子樹，取值范圍為： [root.val,+∞)。

《數據結構與算法》深度精講課程正式上線啦！七大核心算法模塊全解析：

?????????? ?鏈表

?????????? ?二叉樹

?????????? ?二分查找、排序

?????????? ?堆、棧、隊列

?????????? ?回溯算法

?????????? ?哈希算法

?????????? ?動態規劃

無論你是備戰筆試面試、提升代碼效率，還是突破技術瓶頸，這套課程都將為你構建扎實的算法思維底座。🔥立即加入學習打卡，與千名開發者共同進階！

• Python編碼實現：https://www.bilibili.com/cheese/play/ss897667807https://www.bilibili.com/cheese/play/ss897667807

• Java編碼實現：https://www.bilibili.com/cheese/play/ss161443488https://www.bilibili.com/cheese/play/ss161443488

• Golang編碼實現：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ss63997

對于二叉樹的相關算法，我們總結了一套【可視化+圖解】方法，依據此方法來解決相關問題，算法變得易于理解，寫出來的代碼可讀性高也不容易出錯。具體也可以參考視頻詳細講解。

今日佳句：長安回望繡成堆，山頂千門次第開。