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

450. 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

解题思路
先找到节点，然后根据该节点的位置来进行删除
如果为叶节点则直接删除
如果只有一个孩子节点，则孩子节点代替它
否则，需要用右子树的最左节点来替代它（或者左子树的最右节点），这里简单用改变节点值来实现，实际情况可以更改指针
运行结果

java代码

/**
 * 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;
        if(root.val == key){
            //对应无孩子节点或只有一个孩子节点
            if(root.left == null) return root.right;
            if(root.right == null) return root.left;
            //寻找右子树的最左节点来进行替代
            int minval=getMin(root.right);
            root.val=minval;
            root.right=deleteNode(root.right,minval);
        }else if(root.val > key){
            root.left=deleteNode(root.left,key);
        }else if(root.val < key){
            root.right=deleteNode(root.right,key);
        }
        return root;
    }

    public int getMin(TreeNode node){
        while(node.left != null){
            node=node.left;
        }
        return node.val;
    }
}