235.二叉搜索树的最近公共祖先
文章：28. 二叉搜索树的最近公共祖先
题目：235. 二叉搜索树的最近公共祖先
【思路】
二叉搜索树：找到一个节点的值在两边的子树、在p和q之间（一定是最近的公共祖先！）
搜索一条边的写法：
1
2
| if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;
|
搜索整个树写法：
1
2
3
| left = 递归函数(root->left);
right = 递归函数(root->right);
left与right的逻辑处理;
|
本题只需要搜索一条边的写法，遇到递归函数的返回值，如果不为空则立即返回
会出现乘积溢出的情况：
1
2
3
| if((root.val - p.val) * (root.val - q.val) <= 0){
return root;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(true){
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{
break;
}
}
return root;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || root.Val == p.Val || root.Val == q.Val{
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)
}
return root
}
|
701.二叉搜索树中的插入操作
文章：29. 二叉搜索树中的插入操作
题目：701. 二叉搜索树中的插入操作
【思路】
在不调整二叉树的结构的前提下，找到空节点插入元素即可。因此我们需要对二叉搜索树进行遍历操作（递归）。
递归三部曲
确定递归函数参数以及返回值
确定终止条件
确定单层递归的逻辑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null){
TreeNode node = new TreeNode(val);
return node;
}
if(root.val > val){
root.left = insertIntoBST(root.left,val);
}
if(root.val < val){
root.right = insertIntoBST(root.right,val);
}
return root;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil{
node := &TreeNode{Val: val}
return node
}
if root.Val > val {
root.Left = insertIntoBST(root.Left,val)
}else{
root.Right = insertIntoBST(root.Right,val)
}
return root
}
|
450.删除二叉搜索树中的节点
文章：30. 删除二叉搜索树中的节点
题目：调整二叉树的结构最难！| LeetCode：450.删除二叉搜索树中的节点_哔哩哔哩_bilibili
【思路】
二编：递归三部曲：
- 确定递归函数及其返回值
- 确定终止条件
- 确定单层递归的逻辑
不可避免的需要去调整二叉树的结构。
第一种情况：没找到要删除的节点
第二种情况：要删除的节点是叶子节点
第三种情况：要删除的节点左子树不空，右子树空\左子树空，右子树不空
第四种情况：要删除的节点左不为空右不为空
回溯：解决单层处理逻辑
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
| class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
return traversal(root,key);
}
public TreeNode traversal(TreeNode root , int key){
if (root == null)return null;
if(root.val == key){
if ( root.left == null && root.right == null){
return null;
}else if (root.left != null &&root.right == null){
return root.left;
}else if (root.left == null &&root.right != null){
return root.right;
}else{
TreeNode cur = root.right ;
while(cur.left!= null)cur = cur.left;
cur.left = root.left;
return root.right;
}
}
if(key < root.val) root.left = traversal(root.left,key);
if(key > root.val) root.right = traversal(root.right,key);
return root;
}
}
|
忘记写单层遍历的逻辑了
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
| func deleteNode(root *TreeNode, key int) *TreeNode {
return traversal(root,key)
}
func traversal(root *TreeNode,key int)*TreeNode{
if root == nil{
return nil
}
if root.Val == key{
if root.Left == nil && root.Right == nil{
return nil
}else if root.Left != nil && root.Right == nil{
return root.Left
}else if root.Left == nil && root.Right != nil{
return root.Right
}else{
cur := root.Right
for cur.Left != nil{
cur = cur.Left
}
cur.Left = root.Left
return root.Right
}
}
root.Left = traversal(root.Left , key)
root.Right = traversal(root.Right,key)
return root
}
|
【算法总结】
- 二叉搜索树的公共祖先：使用递归，同样类似于双指针，当root的值比pq都大的时候进入左子树（小的一侧），root比pq都小的时候进入大的一侧，处于中间时说明是公共祖先
- 二叉搜索树中的插入操作：使用递归，二叉搜索树的特性使我们直接在空节点处插入数值即可，不涉及对树结构的修改。
- 删除二叉搜索树中的节点：使用递归，需要注意区分三种情况。第四种改变结构的情况需要注意，新建一个node节点来操作二叉树与key相等的节点的right节点，将与key相等的节点包含的树都加入进right节点的左节点的left节点（左节点要为空），重新构建好该节点后返回root.right节点（与key相等的节点需要删除）。
