package leetcode.wyj;


import leetcode.model.TreeNode;

/**
 * 给定一个二叉搜索树的根节点 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 LeetCode450 {
    public static void main(String[] args) {
        TreeNode root2 = new TreeNode(2);
        TreeNode root4 = new TreeNode(4);
        TreeNode root3 = new TreeNode(3);
        root3.left = root2;
        root3.right = root4;

        TreeNode root7 = new TreeNode(7);
        TreeNode root6 = new TreeNode(6);
        root6.right = root7;

        TreeNode root = new TreeNode(5);
        root.left = root3;
        root.right = root6;

        deleteNode(root, 3);

    }

    public static 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 {
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            TreeNode rightMin = findRightMin(root.right);
            root.val = rightMin.val;
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }

    /*查找右子数的最小值*/
    public static TreeNode findRightMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}