---

题目1: 二叉搜索树的最近公共祖先

• 题目链接：235. 二叉搜索树的最近公共祖先

---

1- 思路

与二叉树的最近公共祖先思路一致

---

2- 题解

⭐ 二叉搜索树的最近公共祖先 ——题解思路

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null || root==p || root==q){return root;}// 单层TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);if(left==null && right!=null){return right;}else if(left != null && right==null){return left;}else if(left == null && right== null){return null;}else {return root;}}
}

---

题目2: 二叉搜索树中的插入操作

• 题目链接：235. 二叉搜索树的最近公共祖先

---

1- 思路

• 二叉搜索树的插入，所有结点的插入位置在树的叶子结点上。
• 因此添加节点不需要修改二叉搜索树的结构。

递归三部曲

• 1. 递归函数参数及返回值
  • 参数为 对应的 root 和 val，返回值为 TreeNode：递归过程中遇到空向上一层返回当前递归的结果
• 2. 终止条件 && 结果收集
  • 遇到 null 则证明递归找到了插入位置，因此 返回新建的结点
• 3. 单层递归
  • 根据二叉搜索树的性质，当前元素若比 root.val 大则向右递归，若比 root.val 小则向左递归

---

2- 题解

⭐ 二叉搜索树中的插入操作 ——题解思路

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if(root == null){TreeNode newNode = new TreeNode(val);return newNode;}if(root.val>val){root.left = insertIntoBST(root.left,val);}else if(root.val < val){root.right = insertIntoBST(root.right,val);}return root;}
}

---

题目3: 删除二叉搜索树中的节点

• 题目链接：450. 删除二叉搜索树中的节点

---

1- 思路

删除结点有很多情况需要考虑

• ① 没找到需要删除的结点
• 找到删除结点
  • ② 找到删除结点为 叶子结点：左右都为空
  • ③ 需要删除的结点 非叶子结点：左不空 右为空 ——> 让当前结点的父节点指向当前节点的左节点
  • ④ 需要删除的结点 非叶子结点：左为空 右不空 ——> 让当前结点的父节点指向当前结点的右结点
  • ⑤ 🔑需要删除的结点 非叶子结点：_左不空 右不空 _——> 最复杂，如果删除当前结点，则当前结点的 左子树 拼接到 当前结点 的 右结点的最左下的结点 的 左子树上。

疑问

• 如何同时操作当前结点，以及当前节点与父节点的关系？

递归三部曲

• 2. 终止条件
  • 终止条件为找到被删除的节点，因此删除逻辑也在终止条件中

---

2- 题解

⭐ 删除二叉搜索树中的节点 ——题解思路

class Solution {public TreeNode deleteNode(TreeNode root, int key) {// 终止条件if(root==null){return null;}else if(root.val == key){// 四种情况if(root.left!= null && root.right==null){return root.left;}else if(root.left==null && root.right!=null){return root.right;}else if(root.left == null && root.right==null){return null;}else if(root.left!=null && root.right!=null){TreeNode cur = root.right;while(cur.left!=null){cur = cur.left;}cur.left = root.left;root = root.right;return root;}}if(key>root.val){root.right = deleteNode(root.right,key);}if(key<root.val){root.left = deleteNode(root.left,key);}return root;}
}

---