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

一 题目：

二 思路：

根据二叉搜索树的性质

• 如果目标节点大于当前节点值，则去右子树中删除；
• 如果目标节点小于当前节点值，则去左子树中删除；
• 如果目标节点就是当前节点，分为以下三种情况：
  • 其无左子：其右子顶替其位置，删除了该节点；
  • 其无右子：其左子顶替其位置，删除了该节点；
  • 其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。

三 代码：

 public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        //去右边找
        if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else if (key < root.val) {
            //去左边找
            root.left = deleteNode(root.left, key);
        } else {
            //相等情况下，当前节点是需要删除的节点
            if (root.left == null) {
                    //无左孩子
                return root.right;
            }else if (root.right==null){
                return root.left;
            }else if (root.left!=null && root.right!=null){
                //左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。
                // 寻找欲删除节点右子树的最左节点
                TreeNode node=root.right;
                while (node.left!=null){
                    node=node.left;
                }
                node.left=root.left;
                root=root.right;
            }
        }
        return root;
    }