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

迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else {
            //找到了要删除的节点
            //如果左子树为空，返回右子树
            if (root.left == null)
                return root.right;
            if (root.right == null)
                return root.left;
            //说明两个子节点都不为空，我们可以找左子树的最大值，
            //也可以找右子树的最小值替换
            //这里是用右子树的最小值替换
            TreeNode minNode = root.right;
            while(minNode.left != null ) {
                minNode = minNode.left;
            }
            root.val = minNode.val;
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }
}