450. Delete Node in a BST.md

这道题看似简单，其实删除节点的情况很多

• 找节点
  • 没找到
  • 找到right（开删）
    1. 是root
       1. 无左子树：root=root.right
       2. 有左子树：找左子树最大元素替换
    2. 非root
       1. 有左子树：找左子树最大元素替换
       2. 无左子树：根据pre节点删除，
          1. 如果是pre的左儿子，pre.left=pre.right
          2. 右儿子，pre.right=pre.right

/**
 * 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 {
    TreeNode pre=null;
    boolean hasPre=false;
    int leftOrRight=0;
    public TreeNode deleteNode(TreeNode root, int key) {
        
        if(root==null||root.left==null&&root.right==null&&root.val==key){
            return null;//对于空树和孤立节点命中的情况
        }
        TreeNode target=findByKey(root,key);//找
        if(target!=null){//找到
            if(target.left==null){//如果不存在左子树，需要根据pre删除
                if(leftOrRight==1){//target是某节点的右子树
                    pre.right=target.right;
                }
                if(leftOrRight==-1){//target是某节点的左子树
                    pre.left=target.right;
                }
                if(leftOrRight==0){//是根节点
                    root=root.right;
                }
            }else{
                if(target.left.right==null){//左子树的右侧为空，无需深度搜索
                    target.val=target.left.val;
                    target.left=target.left.left;
                }else{
                    target.val=removeBiggestElem(target.left);//深度搜索删除并且返回删除节点的值
                }
            }
        }
        return root;
    }
    TreeNode findByKey(TreeNode root, int key){//根据节点查找，返回目标节点（没有返回null），并且会更新pre节点，方便直接删除
        if(root==null){
            return null;
        }
        if(root.val==key){
            return root;
        }
        if(root.val>key){
            TreeNode res=findByKey(root.left,key);
            if(!hasPre){
                pre=root;
                hasPre=true;
                leftOrRight=-1;
            }
            return res;
        }
        if(root.val<key){
            TreeNode res=findByKey(root.right,key);
            if(!hasPre){
                pre=root;
                hasPre=true;
                leftOrRight=1;
            }
            return res;
        }
        return null;
        
    }
    int removeBiggestElem(TreeNode root){//删除树中最大的元素（保证root.right非空的前提下）
        if(root.right.right==null){
            int res=root.right.val;
            root.right=root.right.left;//右侧没了，将要删除节点的左子树作为right
            return res;
        }
        return removeBiggestElem(root.right);//继续向右走
    }
}