235.二叉搜索树的最近公共祖先
文章：28. 二叉搜索树的最近公共祖先
题目：235. 二叉搜索树的最近公共祖先
【思路】
二叉搜索树：找到一个节点的值在两边的子树、在p和q之间（一定是最近的公共祖先！）
会出现乘积溢出的情况：
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
14
15
16
17
18
| func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil {
return root
}
for{
if root.Val > p.Val && root.Val > q.Val{
root = root.Left
}
if root.Val <p.Val && root.Val <q.Val{
root = root.Right
}
if (root.Val - p.Val) * (root.Val - q.Val) <=0{
return root
}
}
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
| 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)
}
if root.Val < val{
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
}
|
【算法总结】
- 二叉搜索树的公共祖先：使用递归，保证数值为一正一负，则说明数值在当前节点的左右子树！(但是存在数值溢出的风险）我们可以选择break直接返回（条件要严苛一点）。
- 二叉搜索树中的插入操作：使用递归，二叉搜索树的特性使我们直接在空节点处插入数值即可，不涉及对树结构的修改。
- 删除二叉搜索树中的节点：使用递归，需要注意区分三种情况。第四种改变结构的情况需要注意，新建一个node节点来操作二叉树与key相等的节点的right节点，将与key相等的节点包含的树都加入进right节点的左节点的left节点（左节点要为空），重新构建好该节点后返回root.right节点（与key相等的节点需要删除）。
