算法训练Day22|235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点

 1class Solution {
 2    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 3        // root介于p和q之间时进行返回即可
 4
 5       if (root.val > p.val && root.val > q.val) { // root 在p\q的右侧，向左遍历
 6           return lowestCommonAncestor(root.left, p, q);
 7       } 
 8       if (root.val < p.val && root.val < q.val) { // root 在p\q的左侧，向右遍历
 9           return lowestCommonAncestor(root.right, p, q);
10       }
11       return root; // 找到了结果
12    }

 1class Solution {
 2    // 确定递归函数的参数及返回值
 3    public TreeNode insertIntoBST(TreeNode root, int val) {
 4        // 遇到空节点将该值加入其中并返回（确定递归函数的终止条件）
 5        if (root == null) {
 6            TreeNode node = new TreeNode(val);
 7            return node;
 8        }
 9
10        if (val < root.val) {
11            root.left = insertIntoBST(root.left, val);
12        } else if (val > root.val) {
13            root.right = insertIntoBST(root.right, val);
14        } 
15        return root;
16    }
17}

 1class Solution {
 2    public TreeNode deleteNode(TreeNode root, int key) {
 3        if (root == null) { // 如果根节点为空，直接返回null
 4            return null;
 5        }
 6        if (root.val > key) { // 如果根节点的值大于目标值，递归删除左子树中的目标节点
 7            root.left = deleteNode(root.left, key);
 8            return root;
 9        }
10        if (root.val < key) { // 如果根节点的值小于目标值，递归删除右子树中的目标节点
11            root.right = deleteNode(root.right, key);
12            return root;
13        }
14        if (root.val == key) { // 如果根节点的值等于目标值
15            if (root.left == null && root.right == null) { // 如果根节点没有左右子树，直接返回null
16                return null;
17            }
18            if (root.right == null) { // 如果根节点只有左子树，返回左子树
19                return root.left;
20            }
21            if (root.left == null) { // 如果根节点只有右子树，返回右子树
22                return root.right;
23            }
24            TreeNode successor = root.right; // 找到根节点的后继节点
25            while (successor.left != null) { // 后继节点是右子树中最左边的节点
26                successor = successor.left;
27            }
28            root.right = deleteNode(root.right, successor.val); // 递归删除右子树中的后继节点
29            successor.right = root.right; // 将根节点的右子树赋值给后继节点的右子树
30            successor.left = root.left; // 将根节点的左子树赋值给后继节点的左子树
31            return successor;
32        }
33        return root;
34    }
35}