235.二叉搜索樹的最近公共祖先

題目鏈接：235. 二叉搜索樹的最近公共祖先

思路：根據二叉搜索樹的特性，只需要判斷當前節點是否在[p,q]范圍內就可以，如果在這個范圍里，說明當前節點就是其最近公共祖先。

class Solution {// 根據二叉搜索樹特性，只要當前節點在[p,q]范圍內就說明是其最近祖先public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) return null;if (p.val > q.val) {// 保證 p.val <= q.val，便于后續情況討論return lowestCommonAncestor(root, q, p);}if (root.val >= p.val && root.val <= q.val) {// p <= root <= q// 即 p 和 q 分別在 root 的左右子樹，那么 root 就是 LCAreturn root;}if (root.val > q.val) {// p 和 q 都在 root 的左子樹，那么 LCA 在左子樹return lowestCommonAncestor(root.left, p, q);} else {// p 和 q 都在 root 的右子樹，那么 LCA 在右子樹return lowestCommonAncestor(root.right, p, q);}}
}

精簡版：

class Solution {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;}
}

---

701.二叉搜索樹中的插入操作

題目鏈接：701. 二叉搜索樹中的插入操作

思路：如果要遞歸地插入或者刪除二叉樹節點，遞歸函數一定要有返回值，而且返回值需要被正確的接收。

插入的過程可以分兩部分：

1、尋找正確的插入位置，類似 700. 二叉搜索樹中的搜索。

2、把元素插進去，這就要把新節點以返回值的方式接到父節點上。

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {// 找到空位置插入新節點if (root == null) return new TreeNode(val);// if (root.val == val)//     BST 中一般不會插入已存在元素if (root.val < val)root.right = insertIntoBST(root.right, val);if (root.val > val)root.left = insertIntoBST(root.left, val);return root;}
}

---

450.刪除二叉搜索樹中的節點

題目鏈接：450. 刪除二叉搜索樹中的節點

思路：刪除比插入和搜索都要復雜一些，分三種情況：

情況 1：A 恰好是末端節點，兩個子節點都為空，那么它可以當場刪除；

情況 2：A 只有一個非空子節點，那么它要讓這個孩子接替自己的位置；

情況 3：A 有兩個子節點，為了不破壞BST的性質，A 必須找到左子樹中最大的那個節點或者右子樹中最小的那個節點來接替自己，以下的解法是用右子樹中最小節點來替換。

class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (root == null) return null;if (root.val == key) {// 這兩個 if 把情況 1 和 2 都正確處理了// 左子樹為空，直接返回右子樹// 右子樹為空，直接返回左子樹// 這里若左右子樹均為空，也是返回空if (root.left == null) return root.right;if (root.right == null) return root.left;// 處理情況 3 ，左右子樹都不為空// 獲得右子樹最小的節點TreeNode minNode = getMin(root.right);// 刪除右子樹最小的節點root.right = deleteNode(root.right, minNode.val);// 用右子樹最小的節點替換 root 節點minNode.left = root.left;minNode.right = root.right;root = minNode;} else if (root.val > key) {root.left = deleteNode(root.left, key);} else if (root.val < key) {root.right = deleteNode(root.right, key);}return root;}TreeNode getMin(TreeNode node) {// BST 最左邊的就是最小的while (node.left != null) node = node.left;return node;}
}

---