235. 二叉搜索树的最近公共祖先
题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
文档讲解：https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
状态：已完成
思路：利用二叉搜索树的性质判断p和q在哪颗子树中很方便，基于这一结论进行递归
时间复杂度： O ( l o g N ) O(logN) O(logN)；空间复杂度： O ( l o g N ) O(logN) O(logN)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == p || root == q || root == null)
return root;
if(root.val > p.val && root.val > q.val)
return lowestCommonAncestor(root.left, p, q);
else if(root.val < p.val && root.val < q.val)
return lowestCommonAncestor(root.right, p, q);
else
return root;
}
}
701. 二叉搜索树中的插入操作
题目链接：https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/
文档讲解：https://programmercarl.com/0701.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C.html
状态：已完成
思路：利用二叉搜索树的性质，寻找val的父节点，因此需要使用双指针遍历二叉树
时间复杂度：
O
(
l
o
g
N
)
O(logN)
O(logN)；空间复杂度：
O
(
1
)
O(1)
O(1)
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null)
return new TreeNode(val);
TreeNode cur = root, last = root;
while(cur != null){
if(cur.val > val){
last = cur;
cur = cur.left;
}else{
last = cur;
cur = cur.right;
}
}
if(last.val > val)
last.left = new TreeNode(val);
else
last.right = new TreeNode(val);
return root;
}
}
450. 删除二叉搜索树中的节点
题目链接：https://leetcode.cn/problems/delete-node-in-a-bst/description/
文档讲解：https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
状态：需二刷，确定删除节点的逻辑耗费很长时间
思路：由于删除的节点可能是根节点，因此需要一个dummy节点指向root
- 寻找待删除的节点target及其父节点father
- 注意：二叉树中可能不存在待删除的节点，这种情况直接返回root
- 寻找替换节点
- 如果左子树存在，寻找左子树中的最大值cur及其父节点last
- cur为target左儿子：cur.right = target.right，father->cur
- cur为target左子树中的某个节点（右子树为空，左子树未必）
- 删除cur节点：last.right = cur.left
- 删除target节点：cur.left = target.left，cur.right = target.right，father->cur
- 反之，如果右子树存在，寻找右子树中的最小值cur及其父节点last，类比左子树操作
- 如果左右子树均不存在，则直接删除father指向target的指针
- 如果左子树存在，寻找左子树中的最大值cur及其父节点last
- 返回dummy.left
时间复杂度： O ( l o g N ) O(logN) O(logN)；空间复杂度： O ( 1 ) O(1) O(1)
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
TreeNode dummy = new TreeNode(100001,root,null);
TreeNode father = dummy, target = root;
while(target != null && target.val != key){
father = target;
if(target.val > key)
target = target.left;
else
target = target.right;
}
if(target == null)
return root;
if(target.left != null){
TreeNode last = target;
TreeNode cur = target.left;
while(cur.right != null){
last = cur;
cur = cur.right;
}
if(last == target){
cur.right = target.right;
}else{
last.right = cur.left;
cur.left = target.left;
cur.right = target.right;
}
if(father.left == target)
father.left = cur;
else
father.right = cur;
}else if(target.right != null){
TreeNode last = target;
TreeNode cur = target.right;
while(cur.left != null){
last = cur;
cur = cur.left;
}
if(last != target){
last.left = cur.right;
cur.left = target.left;
cur.right = target.right;
}
if(father.left == target)
father.left = cur;
else
father.right = cur;
}else{
if(father.left == target)
father.left = null;
else
father.right = null;
}
return dummy.left;
}
}