题解 | #删除一个二叉搜索树中的节点#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    
    public Integer findMin(TreeNode root) {
        if (root == null) {
            return null; 
        }
        if (root.left != null) {
            return findMin(root.left);
        } else {
            return root.val;
        }
    } 
    
    
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param key int整型 
     * @return TreeNode类
     */
    public TreeNode deleteNode (TreeNode root, int key) {
        // write code here
        // 二叉树的节点为空
        if (root == null) {
            return root;
        }
        // 当前节点的值与key进行比较，找key值的节点
        if (root.val < key) {
            // 在root的右子树中查找
            root.right = deleteNode(root.right, key);
        } else if (root.val > key) {
            // 在root的左子树中查找
            root.left = deleteNode(root.left, key);
        } else {
            // 找到了key，key节点有三种情况
            // 1.有左右子树
            // 2.只有左子树
            // 3.只有右子树
            // 4.是叶子节点
            if (root.left != null && root.right != null) {
                // 递归删除节点的右子树，找最小的节点进行替换
                root.val = findMin(root.right);
                root.right = deleteNode(root.right, root.val);
            } else {
//                 if (root.left == null && root.right == null) {
//                     root = null;
//                 } else if (root.left != null) {
//                     root = root.left;
//                 } else if (root.right != null) {
//                     root = root.right;
//                 }
                root = root.left != null ? root.left : root.right;
            }
        }
        return root;
    }
}