今天是LeetCode專題第63篇文章，我們一起來聊聊LeetCode中的第98題，二叉搜尋樹的合法性判斷問題。和之前介紹過的幾道題類似，也是一道關于二叉搜尋樹的問題。
本題的官方難度是Medium，點贊4167，反對552，差評率比之前的兩道題稍稍高了一點點，稱得上是一道多半好評的題目。通過率27.7%相比之前40%以上的通過率，這道題的通過率算是Medium難度的題目中偏低的，也就意味着這道題相對困難一些，但題意還是很正的，和之前一樣沒有奇怪的邏輯，考察的就是樸實的了解。
題意
題意很簡單，給定一棵二叉樹要求判斷它是否是一棵合法的二叉搜尋樹（BST)。
一棵合法的二叉搜尋樹需要滿足三個條件：
- 左子樹中的所有節點小于根節點
- 右子樹中的所有節點大于根節點
- 不存在兩個節點的值相等
樣例
2
/ \
1 3
Input: [2,1,3]
Output: true 複制
5
/ \
1 4
/ \
3 6
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4. 複制
題意
我們第一反應就是通過遞歸來解這道題，遞歸的思路當然是可以的，我們把判斷的邏輯一層層嵌套，通過遞歸的形式讓它自己調用自己，進而大大簡化代碼的編寫。但是這其中有一個問題，就是這道題當中的邏輯關系相對不太容易傳遞。
我們舉一個很簡單的例子：
這是一顆二叉樹，為了簡化，我們把左子樹簡化成了A，右子樹簡化成了B。對于A來說，我們需要保證A當中的所有元素都小于root，然而對于B來說，它需要保證其中所有的元素都大于root。如果我們希望遞歸來實作這個判斷的話，我們需要通過遞歸來周遊A和B當中的所有元素，來一一判斷是否是滿足條件的。
這當然是可行的，但是有一個很大的問題是效率很低。因為對于root來說我們需要周遊一次A和B，對于A和B當的根節點來說，我們又需要周遊一次。這其中有很多的邏輯和計算是重複的，這會帶來大量的浪費，我們要做的是優化算法的流程，讓它變得更優。
其實也很好分析，雖然二叉搜尋樹限制了左子樹和右子樹上所有的元素，但是我們仔細想想，其實不需要每個元素都考慮，隻需要關注左子樹當中最大值和右子樹當中最小值就行了。如果左子樹當中的最大值也小于根節點，右子樹當中的最小值也大于根節點，那麼就一定是合法的。反過來如果左子樹存在比根節點大的數或者是右子樹存在比根小的數就都是非法的。
我們可以通過遞歸來同時維護目前子樹當中的最大值和最小值，隻要用左子樹的最大值和右子樹的最小值和根節點進行校驗即可。
附上代碼：
import sys
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def dfs(node):
if node is None:
return True, -sys.maxsize, sys.maxsize
# 遞歸擷取左右子樹的最大值以及最小值以及是否合法
left, lmax, lmin = dfs(node.left)
right, rmax, rmin = dfs(node.right)
# 如果左右子樹存在非法，直接傳回
if (not left) or (not right):
return False, lmax, rmin
# 否則比較左子樹最大值與右子樹最小值
if lmax >= node.val or rmin <= node.val:
return False, lmax, rmin
return True, max(node.val, rmax), min(node.val, lmin)
return dfs(root)[0] 複制
這段代碼看起來不長，但是其實不太好寫，尤其是由于Python支援多值傳回，是以一些操作和C++的遞歸不太一緻，對于C++選手來說可能不是非常友好。但核心的原理是我們在遞歸求子樹的最大值和最小值的同時也判斷了子樹是否是一棵合法的子樹，遞歸不難寫但要把這兩個邏輯整合在一起對新手來說可能不太容易，推薦大家最好自己親手寫一次，加深一下了解。
- END -