?作者簡介：大家好，我是車神哥，府學(xué)路18號的車神?
?About—>車神：從寢室到實(shí)驗(yàn)室最快3分鐘，最慢3分半（那半分鐘其實(shí)是等紅綠燈）
?個人主頁：應(yīng)無所住而生其心的博客_府學(xué)路18號車神_CSDN博客
?點(diǎn)贊?評論?收藏 == 養(yǎng)成習(xí)慣（一鍵三連）?
?本系列主要以刷LeetCode（力扣）網(wǎng)站的各類題為標(biāo)準(zhǔn)，實(shí)現(xiàn)自我能力的提升為目標(biāo)?
?希望大家多多支持?~一起加油 ?

• 專欄—>《LeetCode天梯》

其他專欄：

• 《Neural Network》
• 《Python》
• 《Algorithm》

今天項(xiàng)目終于結(jié)題了，哇，熬了一晚上的夜，夜都被熬熟了，結(jié)題撒花，中午休息了下，下午繼續(xù)卷起來呀，小伙伴們一起來。刷題不止，拒絕?內(nèi)卷，從我做起，哈哈哈，堅(jiān)持吧！～

每天進(jìn)步一點(diǎn)點(diǎn)，就已經(jīng)很棒很棒了，堅(jiān)持堅(jiān)持，不要太累，拒絕內(nèi)卷，從每日一練開始，每天十分鐘，快樂生活一輩子！疫情依舊反復(fù)，大家?guī)Ш每谡职 繼續(xù)繼續(xù)，來，今天和車神哥一起來提升自己的Python編程和面試能力吧，刷天梯~

放上我拍的Photo吧！~ 今天喝了 luckin coffee

每日推薦一首歌：ゆうべは俺が悪かった

以下為我的天梯積分規(guī)則：

每日至少一題：一題積分+10分
若多做了一題（或多一種方法解答），則當(dāng)日積分+20分（+10+10）
若做了三道以上，則從第三題開始算+20分（如：做了三道題則積分-10+10+20=40；做了四道題則積分–10+10+20+20=60）

---

初始分為100分
若差一天沒做題，則扣積分-10分（周六、周日除外注：休息）
堅(jiān)持?。?！

初級算法

刷題目錄

鏈表

題干

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

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

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

示例 1：

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

示例2：

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

提示：

• 樹中節(jié)點(diǎn)數(shù)目范圍在[1, 10^4] 內(nèi)
• -2^31 <= Node.val <= 2^31 - 1

中序遍歷

分析：

可能由讀者不知道中序遍歷是什么，我們這里簡單提及一下，中序遍歷是二叉樹的一種遍歷方式，它先遍歷左子樹，再遍歷根節(jié)點(diǎn)，最后遍歷右子樹。而我們二叉搜索樹保證了左子樹的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。（引用自了力扣原始解釋，這個解釋很通透?。?/p>

class Solution:    def isValidBST(self, root: TreeNode) -> bool:  		if not root:            return True                prev = None         stack = []        while stack or root:            while root:                stack.append(root)                root = root.left            root = stack.pop()            # 若中序遍歷得到的節(jié)點(diǎn)的值小于前一個值prev，那么就說明不是二叉搜索樹，返回False            if prev and root.val <= prev.val:                return False                # 保存上一節(jié)點(diǎn)            prev = root            root = root.right        return True

這個速度超級快，超過100%?。?！

思路很不錯?。?！多多練習(xí)

二叉樹搜索（遞歸）

有大佬分析的很透徹，來看下面的圖

注意6這個節(jié)點(diǎn)不光要小于15而且還要大于10，所以這里的每一個節(jié)點(diǎn)都是有一個范圍的。這里我們來給每個節(jié)點(diǎn)添加一個范圍，如果不在這個范圍之內(nèi)直接返回false，比如6的范圍是(10,15)，很明顯他不在這個范圍內(nèi)，所以他不是二叉搜索樹。下面方法可能不完全按照上面解釋一致。

class Solution:    prev = None  # 用于記錄前一個節(jié)點(diǎn)    def isValidBST(self, root: TreeNode) -> bool:        if not root:            return True        # 從左開始遞歸        if not self.isValidBST(root.left):            return False        # 判斷前一節(jié)點(diǎn)是否大于當(dāng)前        if self.prev is not None and self.prev.val >= root.val:            return False        # 保存前個節(jié)點(diǎn)        self.prev = root        # 右邊遞歸        if not self.isValidBST(root.right):            return False        return True

增加上下界的寫法：

class Solution:    def isValidBST(self, root: TreeNode) -> bool:    # 遞歸并引入上界，下界來判斷是否有效的二叉搜索樹		def chesh(node, min_val = float("-inf"), max_val = float("inf")) -> bool:            if not node:                return True            #每個節(jié)點(diǎn)如果超過這個范圍，直接返回false,設(shè)置出口            if node.val <= min_val or node.val >= max_val:                return False            #這里再分別以左右兩個子節(jié)點(diǎn)分別判斷            #左子樹范圍的最小值是minVal，最大值是當(dāng)前節(jié)點(diǎn)的值，也就是root的值，因?yàn)樽笞訕涞闹狄犬?dāng)前節(jié)點(diǎn)小		            #右子數(shù)范圍的最大值是maxVal，最小值是當(dāng)前節(jié)點(diǎn)的值，也就是root的值，因?yàn)橛易訕涞闹狄犬?dāng)前節(jié)點(diǎn)大            return chesh(node.left, min_val, node.val) and chesh(node.right, node.val, max_val)        return chesh(root)

復(fù)現(xiàn)大佬的Java代碼。

今天到這吧，加油?

Reference

作者：力扣 (LeetCode)
鏈接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnarn7/
來源：力扣（LeetCode）

作者：數(shù)據(jù)結(jié)構(gòu)和算法
鏈接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnd69e/?discussion=1Pu6Hw
來源：力扣（LeetCode）

今日得分：+10+10+20
總得分：690

加油?。?！

?堅(jiān)持讀Paper，堅(jiān)持做筆記，堅(jiān)持學(xué)習(xí)，堅(jiān)持刷力扣LeetCode??。。?br /> 堅(jiān)持刷題?。?！打天梯?。?！
?To Be No.1

??哈哈哈哈

---

?創(chuàng)作不易?，過路能?關(guān)注、收藏、點(diǎn)個贊?三連就最好不過了

?( ′???` )

?

『
縱使天光終將熄滅，我們也要歌頌太陽。
』