package 二叉树.二叉搜索树;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
 * https://leetcode-cn.com/problems/delete-node-in-a-bst/
 * 
 * @author Huangyujun
 *
 */
public class _450_删除二叉搜索树中的节点 {
    //前驱、后驱离当前要删除的结点最近
    class Solution {
        //后驱
        public int successor(TreeNode root) {
            root = root.right;
            while (root.left != null)
                root = root.left;
            return root.val;
        }
        //前驱
        public int predecessor(TreeNode root) {
            root = root.left;
            while (root.right != null)
                root = root.right;
            return root.val;
        }
        //删除值大于 根值，则只能在左子树删除目标，删除值小于根值，只能子啊右子树删除目标
        //当删除的目标就是根值时，考虑：① 根是叶子 【根置空】  ② 有右子树 【根用后驱结点值覆盖，然后对右子树的重复结点进行删除】 ③ 没有右子树【只能到左子树找了，根用前驱结点值覆盖，然后对左子树的重复结点进行删除】  
        public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null)
                return null;
            if (key > root.val)
                root.right = deleteNode(root.right, key);
            else if (key < root.val)
                root.left = deleteNode(root.left, key);
            // delete the current node
            else {
                //找到了，（1）是叶子结点
                // the node is a leaf
                if (root.left == null && root.right == null)
                    root = null;
                // the node is not a leaf and has a right child
                ////找到了，（2）不是是叶子结点（但是有右子树）
                //先通过后驱结点将值覆盖掉找到的结点，然后删除右孩子
                else if (root.right != null) {
                    root.val = successor(root);
                    root.right = deleteNode(root.right, root.val);
                }
                // the node is not a leaf, has no right child, and has a left child
                else {
                    root.val = predecessor(root);
                    root.left = deleteNode(root.left, root.val);
                }
            }
            return root;
        }
    }    
}