二叉樹的第七天妥曲！
題目鏈接：235. 二叉搜索樹的最近公共祖先
狀態(tài)：看視頻講解后一次性AC
利用二叉搜索樹的性質(zhì)可以很容易的尋找p與q的公共祖先的位置。所以如果用遞歸的方法的話钦购，就是遞歸三部曲：參數(shù)就是root檐盟， p， q三個節(jié)點押桃，其中在每次遞歸時葵萎，root傳入的都是當前層次的下一個節(jié)點，例如root.left或root.right。終止條件就是遞歸到root.val介于p.val與q.val之間羡忘。單層遞歸邏輯是如果root.val同時大于p.val和q.val谎痢，就向左節(jié)點遞歸；如果root.val同時小于p.val和q.val就向右節(jié)點遞歸卷雕。迭代法也是這個思路节猿。本題關鍵在于為什么滿足 root.val介于p.val與q.val之間 （這個條件） 的第一個節(jié)點就一定是最近公共祖先？這個這樣理解：root的值介于p q 之間漫雕，那p, q 一定是一個在root的左子樹滨嘱，另一個在root的右子樹中。所以無論往左或者往右再遞歸一層浸间，都不再是另一個節(jié)點的祖先太雨，（即錯過另外一個）完整代碼如下：
class Solution { // Java
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
return root;
}
}
復雜度分析：
時間復雜度：O(h). h為樹高， 樹高決定遞歸深度
空間復雜度：O(h). h為樹高魁蒜， 同上
題目鏈接：701. 二叉搜索樹中的插入操作
狀態(tài)：一次性AC
本題可能最難想的點就在于如何添加 或 在哪插入節(jié)點了囊扳，但是想清楚無論何種情況，都可以在葉子節(jié)點找到合適的位置添加元素兜看，這題就很簡單了宪拥。因為題目也沒說是添加之后要變成平衡二叉樹。
所以思路也很簡單铣减，根據(jù)數(shù)值的大小她君，利用二叉搜索樹的性質(zhì)，一直遞歸到底層然后添加節(jié)點葫哗。
所以遞歸的方法中缔刹，參數(shù)就是節(jié)點root和添加的數(shù)值val。遞歸結(jié)束的條件就是找到空節(jié)點劣针。單層遞歸邏輯就是根據(jù)值的大小找尋正確的方向校镐，值比當前節(jié)點的值大就往右邊找，值比當前節(jié)點的值小就往左邊找捺典。完整代碼如下：
class Solution { // Java
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null) return new TreeNode(val);
if(root.val < val){
root.right = insertIntoBST(root.right, val);
}else if(root.val > val){
root.left = insertIntoBST(root.left, val);
}
return root;
}
}
復雜度分析：
時間復雜度：O(h). h為樹高鸟廓， 樹高決定遞歸深度
空間復雜度：O(h). h為樹高， 同上
題目鏈接：450. 刪除二叉搜索樹中的節(jié)點
狀態(tài)：看了教程襟己，跟著代碼敲引谜，才AC。還得細細琢磨
本題難點在于刪除節(jié)點會改變樹的結(jié)構(gòu)擎浴，因此得列舉出每一種情況才好應對员咽。教程里說一共是有五種情況：
- 沒找到刪除的節(jié)點，遍歷到空節(jié)點就直接返回了贮预。接下來都是找到刪除的節(jié)點的情況了：
- 左右孩子都為空贝室，直接刪除節(jié)點契讲，返回null給上一級
- 左孩子為空，右孩子不為空滑频，刪除節(jié)點后 右孩子補位捡偏，因此返回右孩子給上一級
- 右孩子為空，左孩子不為空峡迷，刪除節(jié)點后 左孩子補位霹琼，因此返回左孩子給上一級
- 左右孩子都不為空，則將刪除節(jié)點左子樹的頭節(jié)點放在 刪除節(jié)點 右子樹的最左邊節(jié)點上凉当，刪除節(jié)點的右孩子為新根節(jié)點枣申。
完整代碼如下：情況二沒有在代碼里有所體現(xiàn)是因為 它被包含在了情況三四中，因為返回的無論是左節(jié)點還是右節(jié)點都是空看杭。
class Solution { // Java
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root; // 情況一：沒找到刪除的節(jié)點
if (root.val == key) {
if (root.left == null) { // 情況三：刪除節(jié)點的左孩子為空忠藤，右孩子不為空
return root.right;
} else if (root.right == null) { // 情況四：刪除節(jié)點的右孩子為空，左孩子不為空
return root.left;
} else { // 情況五：左右孩子節(jié)點都不為空
TreeNode cur = root.right;
while (cur.left != null) {
cur = cur.left;
}
cur.left = root.left;
root = root.right;
return root;
}
}
if (root.val > key) root.left = deleteNode(root.left, key); // 繼續(xù)在左子樹中查找
if (root.val < key) root.right = deleteNode(root.right, key); // 繼續(xù)在右子樹中查找
return root;
}
}
復雜度分析：
時間復雜度：O(h). h為樹高楼雹， 樹高決定遞歸深度
空間復雜度：O(h). h為樹高模孩， 同上
