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

/**
 * 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;
        }
        //2找到了，就删除这个节点
        if(root.val == key){
            //2.1如果只有左子树or只有右子树，那么就返回另一个字数就好了
            // 这样相当于把root的紫薯返回个root的上级，就相当于删除了root
            if(root.left == null){
                return root.right;
            }
            if(root.right == null){
                return root.left;
            }
            //2.2 如果左右子数都有，就需要找后继
            //后继就是，root的right 然后 再一路向左。也就是比root大的全部结点里最小的一个
            TreeNode next = root.right;
            //一路向左
            while (next.left != null) {
                next = next.left;
            }
            //2.3 然后把后继删除，root的位置，使用后继替换，也就是用后继替换root
            root.right = deleteNode(root.right,next.val);
            root.val = next.val;
            return root;
        }
        //检索，如果当前结点比key小，就去右子树检索。否则就去左子树检索
        if(root.val < key){
            root.right =  deleteNode(root.right,key);
        }else {
            root.left =  deleteNode(root.left, key);
        }
        return root;
    }
}