二叉搜索树的最近公共祖先

link：235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

思路分析

题目给出的是二叉搜索树，那就方便很多.（不用在意遍历顺序）
已知左子树的值都比根节点小，右子树的值都比根节点大（每层都符合该规律）但是由于不知道p、q的值哪个比根节点大所以需要进行比较.
我们在递归的时候只需要不断缩小判断区间即可.
怎么缩小呢？
和p、q的值进行比较即可.

递归
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        //缩小 确定范围在左子树
        if(root.val > p.val && root.val > q.val) {
            TreeNode left = lowestCommonAncestor(root.left,p,q);
            //注意判空
            if(left != null) {
                return left;
            }
        }
            //缩小 确定范围在右子树
        if(root.val < p.val && root.val < q.val) {
            TreeNode right = lowestCommonAncestor(root.right,p,q);
            //注意判空
            if(right != null) {
                return right;
            }
        }
        //p、q一个在左一个在右 那就是root是根节点
        return root;
    }
}

二叉搜索树中的插入操作

link：701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

思路分析

根据题目描述遍历比较插入即可，和上题一样可以缩小范围进行判断.
题目又说任意地方插入，我们选插入叶子节点，只要遍历当前节点为空就说明扎到了向上返回即可.

递归
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) {
            TreeNode node = new TreeNode(val);
            return node;
        }
        if(val < root.val) {
            root.left = insertIntoBST(root.left,val);
        }
        if(val > root.val) {
            root.right = insertIntoBST(root.right,val);
        }
        return root;
    }
}

删除二叉搜索树中的节点

link：450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

思路分析

首先找到要删除的节点（如果是叶子节点的话删除不影响）只要不是叶子节点删除可以把右子树中的最小节点（即右子树的最左侧节点）或左子树中的最大节点（即左子树的最右侧节点）上移占位.
找目标删除的节点也可以用相同的方法缩小判断区间.
六种可能性
1.没有匹配key的节点
2.能找到但匹配值的为叶子节点
3.能找到匹配值不为叶子节点但左子树为空右子树也为空
4.能找到匹配值不为叶子节点但左子树不为空右子树为空
5.能找到匹配值不为叶子节点但左子树为空右子树不为空
6.能找到匹配值不为叶子节点但左子树右子树都不为空

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
36
37
38
39
40
41
42
43
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        
        // 找到要删除的节点
        if (root.val == key) {
            // 情况1: 节点是叶子节点
            if (root.left == null && root.right == null) {
                return null;
            }
            // 情况2: 节点只有左子树
            if (root.left != null && root.right == null) {
                return root.left;
            }
            // 情况3: 节点只有右子树
            if (root.left == null && root.right != null) {
                return root.right;
            }
            // 情况4: 节点有两个子树
            if (root.left != null && root.right != null) {
                TreeNode cur = root.right;
                while (cur.left != null) {
                    cur = cur.left;
                }
                // 将左子树连接到右子树的最小节点
                cur.left = root.left;
                // 返回右子树
                return root.right;
            }
        }
        
        // 递归调用
        if (root.val < key) {
            root.right = deleteNode(root.right, key); // 更新右子树
        } else {
            root.left = deleteNode(root.left, 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(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.left;
                //遍历找到左子树最右侧的节点
                while(cur.right != null) {
                    cur = cur.right;
                }
                //将要删除节点的右子树连接到最右侧节点
                cur.right = root.right;
                //更新当前节点为左子树的根节点
                root = root.left;
                return root;
            }
        }
            if(root.val < key) {
                root.right = deleteNode(root.right,key);
            }
            if( key < root.val) {
                root.left = deleteNode(root.left,key);
            }
            return root;
    }
}

Tips
为什么是cur.left = root.left;?
假设我们有如下结构的树.

image-20241118141018034

1
2
3
4
5
TreeNode cur = root.right; // cur 现在指向 7
while (cur.left != null) {
    cur = cur.left; // cur 最终指向 null（右子树最小节点）
}
cur.left = root.left; // 将左子树连接到最小节点