Leetcode面試經典150題刷題記錄 —— 二叉搜索樹篇

這篇具有很好參考價值的文章主要介紹了Leetcode面試經典150題刷題記錄 —— 二叉搜索樹篇。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

Leetcod面試經典150題刷題記錄-系列
Leetcod面試經典150題刷題記錄——數組 / 字符串篇
Leetcod面試經典150題刷題記錄 —— 雙指針篇
Leetcod面試經典150題刷題記錄 —— 矩陣篇
Leetcod面試經典150題刷題記錄 —— 滑動窗口篇
Leetcod面試經典150題刷題記錄 —— 哈希表篇
Leetcod面試經典150題刷題記錄 —— 區(qū)間篇
Leetcod面試經典150題刷題記錄——棧篇
Leetcod面試經典150題刷題記錄——鏈表篇
Leetcod面試經典150題刷題記錄——二叉樹篇
Leetcod面試經典150題刷題記錄——二叉樹層次遍歷篇
本篇：Leetcod面試經典150題刷題記錄——二叉搜索樹篇

遇到二叉搜索樹(BST)的題目，一旦用了sort()直接掛掉面試，切記！

二叉搜索樹性質

二叉搜索樹的性質滿足：
(1)左節(jié)點 > root > 右節(jié)點 (局部性質)
(2)左子樹所有節(jié)點 > root > 右子樹所有節(jié)點 (全局性質，該性質包括局部性質，所以更重要)
相當部分程序員寫起上面的局部性質很容易，寫全局性質的判斷就容易犯病，不瞞你說，我也是。

1. 二叉搜索樹的最小絕對差

題目鏈接：二叉搜索樹的最小絕對差 - leetcode
題目描述：
給你一個二叉搜索樹的根節(jié)點 root ，返回樹中任意兩不同節(jié)點值之間的最小差值。差值是一個正數，其數值等于兩值之差的絕對值。
題目歸納：

解題思路：
解法： 驗證二叉搜索樹 - leetcode官方題解

臟亂差版本

# 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

# 返回二叉搜索樹中，任意兩個不同節(jié)點值之間的最小差值
# 性質
# (1)二叉搜索樹。題目既然說了，那么肯定要用到該性質
# (2)任意兩個不同節(jié)點值，強調了任意兩個不同節(jié)點。但是既然是二叉搜索樹了，拿右子樹中的節(jié)點 - 左子樹中的節(jié)點肯定不會是答案，所以這里的任意其實是帶引號的"任意"，不是絕對的"任意"，是可以忽略一些情況的"任意"

# 以root節(jié)點為例，要查找的目標點一定是下面兩種情況
# (1)左樹的最右節(jié)點 = 左樹的最大節(jié)點 = 中序遍歷的前驅pre節(jié)點
# (2)右樹的最左節(jié)點 = 右樹的最大節(jié)點 = 中序遍歷的后繼post節(jié)點
# 最后遞歸搜索
class Solution:
    def getMinDistance(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        
        # (1)查找左樹的最'右'節(jié)點 = 左樹的最大節(jié)點
        LR = root.left
        while LR and (LR.left or LR.right):
            # 有右邊找右邊，沒右邊找左邊再找右邊
            if LR.right:
                LR = LR.right
            else:
                break
        
        # (2)查找右樹的最'左'節(jié)點 = 右樹的最大節(jié)點
        RL = root.right
        while RL and (RL.left or RL.right):
            if RL.left:
                RL = RL.left
            else:
                break

        left_result = 1e9
        if LR:            left_result = abs(root.val-LR.val)
        right_result = 1e9
        if RL:            right_result = abs(root.val-RL.val)
        return min(left_result, right_result)

    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        result = 1e9

        # 逐個遍歷
        queue = deque([root])
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft() 
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
                
                dis = self.getMinDistance(node)
                result = min(result, dis)
        return result

優(yōu)雅版本

# 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 __init__(self):
        self.result = float('inf')
        self.pre = None

    def traversal(self, cur):
        if cur is None:
            return None
        
        self.traversal(cur.left)  # 左
        
        if self.pre:  # 中
            self.result = min(self.result, cur.val - self.pre.val)
        self.pre = cur  # 記錄前一個
        
        self.traversal(cur.right)  # 右

    def getMinimumDifference(self, root):
        self.traversal(root)
        return self.result

2. 二叉搜索樹中第K小的元素

題目鏈接：二叉搜索樹中第K小的元素 - leetcode
題目描述：
給定一個二叉搜索樹的根節(jié)點 root ，和一個整數 k ，請你設計一個算法查找其中第 k 個最小元素（從 1 開始計數）。
題目歸納：
中序遍歷BST成有序數組，然后再找到這個有序數組的第k個元素？NoNoNo。掌握遞歸轉換成迭代的關鍵思想，即將"函數調用棧"明寫在代碼里。

解題思路：
解法： 二叉搜索樹中第K小的元素 - leetcode官方題解
中序遍歷的迭代寫法，注意，非遞歸！

# 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

# 這道題掌握兩個知識點
# (1)中序遍歷的迭代寫法。即將函數調用棧明示出來，因為函數調用棧也是個棧，所有的遞歸寫法都是可以轉換為迭代版寫法的，手動模擬函數調用棧即可。
# (2)二叉搜索樹的中序遍歷是有序的。

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        # 中序遍歷，迭代版而非遞歸
        stack = []
        while root or stack:
            # 相當于遞歸版寫法的左子樹遍歷
            while root: # 壓棧方向是單一的，沿著二叉樹的右上角->左下角方向壓棧
                stack.append(root)
                root = root.left
            root = stack.pop() # 遇到空就出棧
            # if root: print(root.val)
            k -= 1
            if k == 0:
                return root.val
            root = root.right

3. 驗證二叉搜索樹

題目鏈接：驗證二叉搜索樹 - leetcode
題目描述：
給定一個二叉樹的根節(jié)點 root，想象自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節(jié)點值。
題目歸納：
右視圖 = 右邊的側視圖

解題思路：
解法： 驗證二叉搜索樹 - leetcode官方題解
(1) 從左到右層序遍歷。記錄層序遍歷的最后一個node，即為右視圖看到的第一個node。

經典錯誤(從局部性質推斷全局性質)

# 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: Optional[TreeNode]) -> bool:
        # 這是一道21年的408考研真題，空節(jié)點和葉節(jié)點都是二叉搜索樹
        # 注意下面的寫法是錯誤的，原因在于只判斷了局部的性質，而忽略了全局的性質
        if not root: return True
        if not root.left and not root.right: return True
        
        # (1)這個時候root肯定存在，左樹或許存在，結合root與左樹根節(jié)點，判斷是不是二叉搜索樹
        if root and root.left and root.left.val < root.val:
            return self.isValidBST(root.left)
        else:
            return False

        # (2)這個時候root肯定存在，右樹或許存在，結合root與右樹根節(jié)點，判斷是不是二叉搜索樹
        if root and root.right and root.val < root.right.val:
            return self.isValidBST(root.right)
        else:
            return False

利用第1題的代碼(有pre指針的那段)

# 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 __init__(self):
        self.pre = None

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        left = self.isValidBST(root.left)
        
        if self.pre and self.pre.val >= root.val: # __比第1題加了這個判斷__
            return False
        self.pre = root # 要遍歷root.right了，這個時候記錄pre節(jié)點
        
        right = self.isValidBST(root.right)
        
        return left and right # 兩邊都要是BST樹

附加題

1. 不同的二叉搜索樹

題目鏈接：不同的二叉搜索樹 - leetcode
題目描述：
給你一個整數 n ，求恰由 n 個節(jié)點組成且節(jié)點值從 1 到 n 互不相同的二叉搜索樹有多少種？返回滿足題意的二叉搜索樹的種數。
題目歸納：
分治+動態(tài)規(guī)劃

解題思路：
解法： 不同的二叉搜索樹 - leetcode官方題解文章來源地址http://www.zghlxwxcb.cn/news/detail-819389.html

class Solution:
    def numTrees(self, n: int) -> int:
        # 給一個整數n，求恰好由n個節(jié)點組成，且節(jié)點值從1到n，能夠組成多少種不同的二叉搜索樹。
        #給定一個有序序列1...n，遍歷數字i，將數字i作為root，1 ... (i-1)序列作為左子樹，(i+1) ... n作為右子樹，接著按照同樣的方式遞歸構建左子樹和右子樹
        # 在上述構建過程中，由于根root值不同，因此能保證每棵BST是唯一的。
        
        # 采用動態(tài)規(guī)劃來求解本題
        # G(n): 長度為n的序列，所能構成的不同的BST樹的個數。注意到 G(n) 和序列的內容無關，只和序列的長度有關
        # F(i,n)：以i為根、序列長度為n的不同BST的個數
        # G(n) = sum_{1}^{n}F(i,n)
        # 特別的: G(0) = 1 , G(1) = 1
        # F(i,n) = G(i-1)*G(n-i)
        # ==> G(n) = sum_{1}^{n}G(i-1)G(n-i)
        G = [0] * (n+1)
        G[0] = 1
        G[1] = 1
        for i in range(2, n+1):
            for j in range(1, i+1):
                G[i] += G[j-1] * G[i-j]
        return G[n]