回顧二分搜索樹的定義
二分搜索樹的重要性質(zhì)
二分搜索樹的重要性質(zhì)如下宠蚂，初學的時候經(jīng)常會被忽略或者錯誤地理解：
- 左子樹中所有的結(jié)點都小于當前結(jié)點；
- 右子樹中所有的結(jié)點都大于當前結(jié)點宪潮。
- 以左右孩子為根的子樹仍為二分搜索樹。
回顧二分搜索樹中的基本操作
既然學習到這個專題趣苏，我們就有必要來復(fù)習鞏固之前在學習《二分搜索樹》的時候所進行的一些基本操作坎炼，這些操作都是十分重要而且基礎(chǔ)的。由于二分搜索樹的性質(zhì)拦键，我們總能以 時間復(fù)雜度來完成上面的操作谣光。
1、插入 insert
2芬为、查找 find
3萄金、刪除 delete
4、最大值媚朦，最小值 minimum, maximum
5氧敢、前驅(qū)，后繼 successor, predecessor
6询张、上界孙乖，下界 floor, ceil
7、某個元素的排名 rank
8份氧、尋找第 k大（形ò馈）元素 select
9、如何將二分搜索樹改造成平衡搜索樹蜗帜，平衡搜索樹的一個重要應(yīng)用就是紅黑樹恋拷。
例題
例1：LeetCode 第 235 題（尋找二分搜索樹中指定兩個結(jié)點的最近公共祖先）
傳送門：英文網(wǎng)址：235. Lowest Common Ancestor of a Binary Search Tree ，中文網(wǎng)址：235. 二叉搜索樹的最近公共祖先 厅缺。
給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先蔬顾。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p宴偿、q，最近公共祖先表示為一個結(jié)點 x诀豁，滿足 x 是 p窄刘、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）∠鲜ぃ”
例如都哭，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]
LeetCode 第 235 題（尋找二分搜索樹中指定兩個結(jié)點的最近公共祖先）示例 1:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 輸出: 6 解釋: 節(jié)點 2 和節(jié)點 8 的最近公共祖先是 6。示例 2:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 輸出: 2 解釋: 節(jié)點 2 和節(jié)點 4 的最近公共祖先是 2, 因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身逞带。說明:
- 所有節(jié)點的值都是唯一的欺矫。
- p、q 為不同節(jié)點且均存在于給定的二叉搜索樹中展氓。
分析：這道題只要我們分析清楚遞歸關(guān)系穆趴，其實是非常簡單的。就是利用了我們在本文開頭部分所敘述的“二分搜索樹的重要性質(zhì)”來進行分類討論遇汞。
1未妹、如果 p、q 結(jié)點位于 root 結(jié)點的同一側(cè)空入，如果位于左側(cè)络它，則遞歸地調(diào)用左孩子，如果位于右側(cè)歪赢，則遞歸地調(diào)用右孩子化戳；
2、如果 p埋凯、q 結(jié)點位于 root 結(jié)點的兩側(cè)点楼，則所求的最近的公共祖先就是 root 自己；
3掠廓、如果 p蟀瞧、q 其中之一位于 root 結(jié)點悦污，則 root 結(jié)點即為所求的結(jié)點屈溉。
解答
Java 代碼：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null){
return null;
}
if(p.val < root.val && q.val < root.val){
return lowestCommonAncestor(root.left,p,q);
}
if(p.val > root.val && q.val > root.val){
return lowestCommonAncestor(root.right,p,q);
}
return root;
}
}
總結(jié)
這道問題的實現(xiàn)有賴于我們對二分搜索樹的深刻的理解以及我們對整個問題的邏輯分析帆赢。
相關(guān)練習
練習1：LeetCode 第 98 題：驗證 BST
傳送門：英文網(wǎng)址：98. Validate Binary Search Tree 椰于，中文網(wǎng)址：98. 驗證二叉搜索樹 瘾婿。
給定一個二叉樹偏陪，判斷其是否是一個有效的二叉搜索樹煮嫌。
假設(shè)一個二叉搜索樹具有如下特征：
- 節(jié)點的左子樹只包含小于當前節(jié)點的數(shù)昌阿。
- 節(jié)點的右子樹只包含大于當前節(jié)點的數(shù)。
- 所有左子樹和右子樹自身必須也是二叉搜索樹灶轰。
示例 1:
輸入: 2 / \ 1 3 輸出: true示例 2:
輸入: 5 / \ 1 4 / \ 3 6 輸出: false 解釋: 輸入為: [5,1,4,null,null,3,6]笋颤。 根節(jié)點的值為 5 内地，但是其右子節(jié)點值為 4 瓤鼻。
分析：二分搜索樹定義 3 條茬祷，根據(jù)定義判斷其實是最簡單的祭犯，在技巧上就是要分一下粥惧，是左子樹還是右子樹突雪；
練習2：LeetCode 第 450 題：刪除二叉搜索樹中的節(jié)點
傳送門：英文網(wǎng)址：450. Delete Node in a BST 咏删，中文網(wǎng)址：450. 刪除二叉搜索樹中的節(jié)點 督函。
給定一個二叉搜索樹的根節(jié)點 root 和一個值 key嘀粱，刪除二叉搜索樹中的 key 對應(yīng)的節(jié)點，并保證二叉搜索樹的性質(zhì)不變锋叨。返回二叉搜索樹（有可能被更新）的根節(jié)點的引用宛篇。
一般來說娃磺，刪除節(jié)點可分為兩個步驟：
- 首先找到需要刪除的節(jié)點；
- 如果找到了豌鸡，刪除它。
說明： 要求算法時間復(fù)雜度為 O(h)段标，h 為樹的高度涯冠。
示例:
root = [5,3,6,2,4,null,7] key = 3 5 / \ 3 6 / \ \ 2 4 7 給定需要刪除的節(jié)點值是 3，所以我們首先找到 3 這個節(jié)點蛇更，然后刪除它缎岗。 一個正確的答案是 [5,4,6,2,null,null,7], 如下圖所示译打。 5 / \ 4 6 / \ 2 7 另一個正確答案是 [5,2,6,null,4,null,7]壁袄。 5 / \ 2 6 \ \ 4 7
分析：刪除結(jié)點是一個比較復(fù)雜的操作豆混，一定要會皿伺。給定一棵二分搜索樹盒粮，刪除其中的一個結(jié)點鸵鸥。若刪除的結(jié)點不存在？是否可能有多個需要刪除的結(jié)點丹皱，刪除的結(jié)點是否需要返回妒穴？
這個問題我以前專門寫了題解宋税，請點擊這里。
練習3： LeetCode 第 108 題： 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
傳送門：108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹宰翅。
將一個按照升序排列的有序數(shù)組弃甥，轉(zhuǎn)換為一棵高度平衡二叉搜索樹爽室。
本題中汁讼，一個高度平衡二叉樹是指一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過 1。
示例:
給定有序數(shù)組: [-10,-3,0,5,9], 一個可能的答案是：[0,-3,9,-10,null,5]阔墩，它可以表示下面這個高度平衡二叉搜索樹： 0 / \ -3 9 / / -10 5
Python 代碼：
# 108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
# Definition for a binary tree node.
# 將一個按照升序排列的有序數(shù)組嘿架，轉(zhuǎn)換為一棵高度平衡二叉搜索樹。
# 本題中啸箫，一個高度平衡二叉樹是指一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過 1耸彪。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if len(nums) == 0:
return None
return self.__helper(nums, 0, len(nums) - 1)
def __helper(self, nums, left, right):
# 寫遞歸問題是有套路的，先寫遞歸終止條件忘苛，然后再寫遞歸流程
if left > right:
return None
if left == right:
return TreeNode(nums[left])
mid = left + (right - left) // 2
root = TreeNode(nums[mid])
root.left = self.__helper(nums, left, mid - 1)
root.right = self.__helper(nums, mid + 1, right)
return root
練習4： LeetCode 第 230 題：二叉搜索樹中第K小的元素
傳送門：英文網(wǎng)址：230. Kth Smallest Element in a BST 蝉娜，中文網(wǎng)址：230. 二叉搜索樹中第K小的元素 。
給定一個二叉搜索樹扎唾，編寫一個函數(shù)
kthSmallest來查找其中第 k 個最小的元素召川。說明：
你可以假設(shè) k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個數(shù)胸遇。示例 1:
輸入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 輸出: 1示例 2:
輸入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 輸出: 3進階：
如果二叉搜索樹經(jīng)常被修改（插入/刪除操作）并且你需要頻繁地查找第 k 小的值荧呐，你將如何優(yōu)化kthSmallest函數(shù)？
分析：因為二分搜索樹具有順序性纸镊，所以我們可以用類似快速排序的 partition 操作來完成
1倍阐、二分搜索樹的有序性；2逗威、二叉樹中序遍歷峰搪，特別地，二分搜索樹的中序遍歷得到的是一個有序數(shù)組凯旭。
簡而言之就是在中序遍歷的時候數(shù)個數(shù)概耻，第 1 個遍歷到的是第 1 個最小的元素，第 2 個遍歷到的是第 2 個最小的元素尽纽，數(shù)到第 k 個夠數(shù)了咐蚯，就不用再遍歷了。
Python 代碼：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 230. 二叉搜索樹中第K小的元素
# 給定一個二叉搜索樹弄贿，編寫一個函數(shù) kthSmallest 來查找其中第 k 個最小的元素春锋。
class Solution:
# 使用中序遍歷得到 BST 第 k 小的那個元素
def __init__(self):
self.k = None
self.res = None
def __dfs(self, node):
if node is None:
return
self.__dfs(node.left)
self.k -= 1
if self.k == 0:
self.res = node.val
return
self.__dfs(node.right)
def kthSmallest(self, root, k):
self.k = k
self.__dfs(root)
return self.res
等價寫法：
Python 代碼：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.counter = 0
self.res = 0
def kthSmallest(self, root, k):
# 使用遞歸的方法，中序遍歷
if root.left:
# 不是空差凹，才繼續(xù)遍歷
self.kthSmallest(root.left, k)
self.counter += 1
# print(root.val)
if self.counter == k:
# 注意：千萬不能在這里返回期奔，后序遍歷還要繼續(xù)進行下去
self.res = root.val
return
if root.right:
self.kthSmallest(root.right, k)
return self.res
Python 代碼：推薦寫法
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 這種寫法比 3 更好一些侧馅，在入棧的時候，就判斷結(jié)點是不是空呐萌，非空才入棧
class Solution:
def kthSmallest(self, root, k):
stack = [(1, root)]
while stack:
command, node = stack.pop()
if command == 0:
k -= 1
if k == 0:
return node.val
else:
# 模擬系統(tǒng)棧實現(xiàn)中序遍歷(先左邊馁痴、再自己、再右邊)
if node.right:
stack.append((1, node.right))
stack.append((0, node))
if node.left:
stack.append((1, node.left))
練習5：LeetCode 第 236 題：二叉樹的最近公共祖先
傳送門：英文網(wǎng)址：236. Lowest Common Ancestor of a Binary Tree 肺孤，中文網(wǎng)址：236. 二叉樹的最近公共祖先 罗晕。
給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p赠堵、q小渊，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p茫叭、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）酬屉。”
例如揍愁，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]
LeetCode 第 236 題：二叉樹的最近公共祖先示例 1:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 輸出: 3 解釋: 節(jié)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3呐萨。示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 輸出: 5 解釋: 節(jié)點 5 和節(jié)點 4 的最近公共祖先是節(jié)點 5。因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身莽囤。說明:
- 所有節(jié)點的值都是唯一的怯屉。
- p饵沧、q 為不同節(jié)點且均存在于給定的二叉樹中锨络。
分析：給定一棵二叉樹和兩個結(jié)點，尋找這兩個結(jié)點的最近公共祖先狼牺。該問題是經(jīng)典的 LCA 問題羡儿。在這里我寫了比較完整的分析過程。
（本節(jié)完）
