代码随想录算法训练营第十九天-235二叉搜索树的最近公共祖先、701二叉搜索树中的插入操作、450删除二叉搜索树中的节点
初步题解
235 二叉搜索树的最近公共祖先
题目链接：(https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree)
看了一部分的解析。主要在于当我们从上向下去递归遍历，第一次遇到 cur 节点是数值在 [q, p] 区间中，那么 cur 就是 q 和 p 的最近公共祖先。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p.val < q.val) {
return lowestCommonAncestorTravel(root, p, q);
} else {
return lowestCommonAncestorTravel(root, q, p);
}
}
private TreeNode lowestCommonAncestorTravel(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || (p.val <= root.val && root.val <= q.val)) {
return root;
} else if (root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
} else {
return lowestCommonAncestor(root.right, p, q);
}
}
|
701 二叉搜索树中的插入操作
题目链接：(https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
TreeNode pre;
public TreeNode insertIntoBST(TreeNode root, int val) {
if (pre == null) {
if (root == null) {
return new TreeNode(val);
}
} else {
if (root == null) {
if (pre.val > val){
pre.left = new TreeNode(val);
} else if (pre.val < val) {
pre.right = new TreeNode(val);
}
return root;
}
}
pre = root;
if (root.val > val) {
insertIntoBST(root.left, val);
} else if (root.val < val) {
insertIntoBST(root.right, val);
}
return root;
}
|
450 删除二叉搜索树中的节点
题目链接：(https://leetcode.cn/problems/delete-node-in-a-bst)
想的是左子树顶位子的情况。看了解析用了右子树顶位，好像确实好理解一点。（包括讲解中的普通二叉树删除，也是用了右子树顶位）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return root;
}
if (root.val == key) {
if (root.left == null) {
root = root.right;
} else if (root.right == null) {
root = root.left;
} else {
TreeNode right = root.right;
TreeNode leftRight = root.left.right;
root = root.left;
if (leftRight != null) {
root.right = leftRight;
root.right.right = right;
} else {
root.right = right;
}
}
return root;
}
if (root.val > key) {
root.left = deleteNode(root.left, key);
} else {
root.right = deleteNode(root.right, key);
}
return root;
}
|
看解析
235 二叉搜索树的最近公共祖先
题目链接/文章讲解：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
视频讲解：[https://www.bilibili.com/video/BV1Zt4y1F7ww](https://www.bilibili.com/video/BV1Zt4y1F7ww
701 二叉搜索树中的插入操作
题目链接/文章讲解：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
视频讲解：https://www.bilibili.com/video/BV1Et4y1c78Y
1
2
3
4
5
6
7
8
9
10
11
12
|
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;
}
|
450 删除二叉搜索树中的节点
题目链接/文章讲解：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
视频讲解：https://www.bilibili.com/video/BV1tP41177us
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root;
if (root.val == key) {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
} else {
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);
if (root.val < key) root.right = deleteNode(root.right, key);
return root;
}
|