450. Delete Node in a BST 删除bst中的一个节点

［抄题］：

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

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

    5
   / 
  3   6
 /    
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / 
  4   6
 /     
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / 
  2   6
      
    4   7

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

不知道怎么删除：把节点的val替换一下就行了

一位要用list添加，结果它是直接把子树存起来了。

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［一句话思路］：

先确定点的位置并进行递归，替换值后继续在右边递归

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

忘记写退出条件了，但树的题首先第一步就应该写退出条件root == null
替换的情况必须要把dc和root节点连起来

［二刷］：

bst中一个数只出现一次，所以继续递归的时候key改成root.val
左右节点为空都属于空的情况，要写在一起

［三刷］：

先是recursive找key的位置，找到key的位置之后再进行替换

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

删除节点就是把节点值替换一下就行了，剩下的用dc补上来

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［算法思想：迭代/递归/分治/贪心］：

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

[是否头一次写此类driver funcion的代码] ：

[潜台词] ：

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        //exit if null
        if (root == null) return null;
        
        //define the recursion's location
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        }else {
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;
            
            //find min and replace
            TreeNode minNode = findMin(root.right);
            root.val = minNode.val;
        
            //continue recursion
            root.right = deleteNode(root.right, root.val);
        }

      return root;
    }
  
    public TreeNode findMin(TreeNode root) {
      while (root.left != null) {
        root = root.left;
      }
      return root;
    }
}

View Code