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

import java.util.*;

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

/**
 * NC297 删除一个二叉搜索树中的节点
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递归
     *
     * @param root TreeNode类
     * @param key int整型
     * @return TreeNode类
     */
    public TreeNode deleteNode (TreeNode root, int key) {
        if(root == null){
            return null;
        }

        if(root.val == key){
            TreeNode node;
            // 无左子树
            if(root.left == null){
                node = root.right;
                root.right = null;
                return node;
            }
            // 无右子树
            if(root.right == null){
                node = root.left;
                root.left = null;
                return node;
            }
            // 左右子树都有
            // curr: 右子树的最左节点
            TreeNode curr = root.right;
            while(curr.left != null){
                curr = curr.left;
            }
            curr.left = root.left;
            root.left = null;
            node = root.right;
            root.right = null;
            return node;
        }else if(root.val > key){
            root.left = deleteNode(root.left, key);
        }else{
            root.right = deleteNode(root.right, key);
        }

        return root;
    }
}