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

一、题目

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。
 

二、解法

node表示找到的节点，prev表示前驱节点。由于node可能就是root，所以要设置一个虚拟头结点vHead。

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode vHead=new TreeNode();
        vHead.left=root;
        TreeNode node=root,prev=vHead;
        while(node!=null&&node.val!=key){
            prev=node;
            if(node.val>key) node=node.left;
            else node=node.right;
        }
        if(node==null) return root;

        TreeNode l=node.left,r=node.right,n;
        if(l!=null&&r!=null){
            TreeNode k=l;
            while(k.right!=null) k=k.right;
            k.right=r.left;
            r.left=l;
            n=r;
        }else{
            n=l==null?r:l;
        }
        if(prev.left==node) prev.left=n;
        else prev.right=n;
        return vHead.left;
    }
}