LeetCode 450. 删除二叉搜索树中的节点

450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

• 首先找到需要删除的节点；
• 如果找到了，删除它。

说明:

要求算法时间复杂度为 O(h)，h 为树的高度。

示例:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

    5
   / \
  4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

    5
   / \
  2   6
   \   \
    4   7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-node-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 创建二叉树

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

• 1. 递归法

思路：

1. 比较当前节点的值和要删除的节点的值，如果 key < root.val， 那么在左子树进行删除
2. 如果 key > root.val, 那么在右子树进行删除
3. 如果相等，则表示找到了要删除的节点，在判断该节点的左子树是否为空，如果是，返回右子树即可
4. 如果右子树为空，则返回左子树即可
5. 如果左右子树都不为空，我们需要找到比待删除节点大的最小节点，也就是右子树中的最小子树，使该节点作为删除后的节点

public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        //要删除的值小于根节点值，那么在左子树中寻找
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
            return root;
        } else if (key > root.val) {   //右子树中查找
            root.right = deleteNode(root.right, key);
            return root;
        } else {    //找到该节点，进行删除
            if (root.left == null) {
                //左子树为空，删除节点，使用右节点替换
                TreeNode rightNode = root.right;
                root.right = null;
                return rightNode;
            } else if (root.right == null) {
                //右子树为空，删除节点，使用左节点替换
                TreeNode leftNode = root.left;
                root.left = null;
                return leftNode;
            } else {
                //左右子树均不为空，需要找到比待删除节点大的最小节点
//                TreeNode successor = minimum(root.right);
//                successor.left = root.left;
//                successor.right = removeMin(root.right);
//                root.left = root.right = null;
                root.val = minimum(root.right).val;
                root.right = removeMin(root.right);
                return root;
            }
        }
    }

    /**
     * 找到二叉搜索树中的最小节点
     * @param node
     * @return
     */
    private TreeNode minimum(TreeNode node) {
        if (node.left == null) return node;
        return minimum(node.left);
    }

    /**
     * 移除二叉搜索树中的最小节点，返回新的二叉搜索树的根
     * @param node
     * @return
     */
    private TreeNode removeMin(TreeNode node) {
        if (node.left == null) {
            TreeNode rightNode = node.right;
            node.right = null;
            return rightNode;
//            return node.right;
        }
        node.left = removeMin(node.left);
        return node;
    }

复杂度分析：

• 时间复杂度：O(log(n)), 也就是树的高度
• 空间复杂度：O(log(n)), 递归深度为树的高度

---

• 源码

• 我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正

• Github