五分钟看懂一道中等难度的算法题

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

        5
       / \
      3   6
     / \   \
    2   4   7
   /         \
  1           8

//五分钟学算法
public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }

    // 当前遍历到的节点大于要找的节点，去左边继续找
    if (root.val > key) {
        root.left = deleteNode(root.left, key);
    }
    // 当前遍历到的节点小于要找的节点，去右边继续找
    else if (root.val < key) {
        root.right = deleteNode(root.right, key);
    } 
    // 找到要删除的节点，进行删除操作
    else {
        // 情况 1 & 2
        if (root.right == null) {
            return root.left;
        } 

        // 情况 3
        if (root.left == null) {
            return root.right;
        }

        // 去到删除节点的右子树，找到值最小的节点
        TreeNode rightSmallest = root.right;
        while (rightSmallest.left != null) {
            rightSmallest = rightSmallest.left;
        }

        // 将删除节点的左子树全部移到这个节点下
        rightSmallest.left = root.left;

        // 返回右子树的根节点，放到当前删除节点的位置
        return root.right;
    }

    return root;
}