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

删除二叉搜索树的节点要比插入一个节点更难，区别在于，我们总能找到一个叶子节点，把我们要插入的值缀在后面。

但是删除节点不总是删除叶子节点，还有可能删除一个中间节点，这就需要额外的操作。

我们需要分情况来讨论。

理解题意：

        删除二叉搜索树的一个节点：找到指定值进行删除，且如果删除的节点是中间节点，则我们需要调整树结构，使他删除后任然是二叉搜索树。

1.删除的是叶子节点：        直接删除

2.删除的是中间节点：

        左子树为空,右子树不为空： 将当前节点替换为右子树

        左子树不为空，右子树为空：将当前节点替换为左子树

        左子树不为空，且右子树不为空： 则有两种操作：

                可以将右子树上移，为左子树找个合适的位置

                可以将左子树上移，为右子树找个合适的位置

3.找不到删除的节点，返回root本身

两种解题方法：

        递归 回溯

1.递归

该题复杂的地方在于分情况讨论，各种情况处理清楚这道题就会简单。

public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null) return null;
        //当找到值时如何删除
        if(root.val==key){
            if(root.left==null&&root.right==null){
                //是叶子直接删除
                return null;
            } else if (root.left!=null&&root.right==null) {
                //非叶子，左不空，右空，左子树上移
                return root.left;
            }else if(root.left==null&&root.right!=null){
                //非叶子，左空，右不空，右子树上移
                return root.right;
            }else{
                //最复杂的一种情况，左不空，右不空，挑一个上移
                //这里挑右子树上移，给左子树一个合理的位置
                TreeNode cur=root.right;
                while(cur.left!=null) cur=cur.left;
                cur.left=root.left;
                return root.right;
            }
        }
        //左子树递归
        root.left=deleteNode(root.left,key);
        //右子树递归
        root.right=deleteNode(root.right,key);
        return root;
    }

2.迭代

迭代实现上来看，思路其实并不难，问题在于如何删除一个节点呢，这里引入一个father指针，总是指向当前节点的父节点，通过和父节点值大小的比较，可以明确当前节点是左孩子还是有孩子。

除此之外，当father==null时，说明当前节点是根节点。

唯一比较复杂的地方在于合理的处理删除节点的操作和各种情况分析。

public TreeNode deleteNode2(TreeNode root, int key) {
        TreeNode father=null;
        TreeNode preFather=null;
        TreeNode cur=root;
        while(cur!=null){
            if(cur.val==key){
                //开启删除操作
                if(cur.left==null&&cur.right==null){
                    //是叶子直接删除
                    if(father!=null&&father.val>key){
                        //删左
                        father.left=null;
                    }else if(father!=null&&father.val<key){
                        //删右
                        father.right=null;
                    }else if(father==null){
                        //是叶子且没有父亲，即为根节点
                        return null;
                    }
                } else if (cur.left!=null&&cur.right==null) {
                    //非叶子，左不空，右空，左子树上移
                    if(father!=null&&father.val>key){
                        //删左
                        father.left=cur.left;
                    }else if(father!=null&&father.val<key){
                        //删右
                        father.right=cur.left;
                    }else if(father==null){
                        return cur.left;
                    }
                }else if(cur.left==null&&cur.right!=null){
                    //非叶子，左空，右不空，右子树上移
                    if(father!=null&&father.val>key){
                        //删左
                        father.left=cur.right;
                    }else if(father!=null&&father.val<key){
                        //删右
                        father.right=cur.right;
                    }else if(father==null){
                        return  cur.right;
                    }
                }else{
                    //最复杂的一种情况，左不空，右不空，挑一个上移
                    //这里挑右子树上移，给左子树一个合理的位置
                    TreeNode node=cur.right;
                    while(node.left!=null) node=node.left;
                    node.left=cur.left;
                    if(father!=null&&father.val>key){
                        //删左
                        father.left=cur.right;
                    }else if(father!=null&&father.val<key){
                        //删右
                        father.right=cur.right;
                    }else if(father==null){
                        return  cur.right;
                    }
                }
                //删除结束跳出
                break;
            } else if (cur.val>key) {
                father=cur;
                cur=cur.left;
            } else if (cur.val<key) {
                father=cur;
                cur=cur.right;
            }
        }
        return root;
    }

3.分析

时间复杂度：

        递归：O(log2N)

        迭代：O(log2N)

空间复杂度：

        递归：O(n)

        迭代：O(n)