My Forty-fourth Page - 删除二叉搜索树中的节点 - By Nicolas

这篇page主要是针对leetcode上的450.删除二叉搜索树中的节点所写的。小尼先简单的说明一下这道题的意思，给定一个二叉搜索树的根节点root和一个值key，删除二叉搜索树重点key对应的节点，并且要求保持二叉搜索树的性质不变，返回二叉搜索树的根节点的引用。

小尼先简单的分析一下这道题的思路，首先呢，我们需要先考虑清楚删除的过程中会发生的几种情况，首先第一种情况就是二叉树中没有我们可以删除的元素，第二种情况是删除的节点对应的左右节点都是空的（都是null的）那么，我们这时直接返回上一个节点即可。第三种情况，就是我们删除的节点对应的左节点为空，右节点不为空，那么我们只需要让该节点等于它的右节点即可。第四种情况，就是我们删除的节点的左节点不为空，右节点为空，那么我们此时只需要将该节点等于它的左节点即可。还有第五种情况就是该节点的左右节点都不为空，那么此时我们应该如何操作，其实也很简单，我我们可以想一下，该节点对应的右子树的所有节点的元素一定比它的左子树对应的节点的元素要大，所以我们可以先遍历该节点的右子树种的最小的元素，采取的方法就是不断地对右子树的部分进行向左的遍历，然后我们再将该节点做左子树的部分放在右子树最小元素的左边，这样，最后我们再root=root.right，在我们将元素放完了之后，因为我们需要将该节点取出，所以我们直接将该节点的位置用该节点的右子树代替即可。

小尼接下来拉一下递归的代码：

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return root;
        if(root.val == key){
            if(root.left == null){
                return root.right;
            }else if(root.right == null){
                return root.left;
            }else{
                TreeNode cur = root.right;
                while(cur.left != null){
                    cur = cur.left;
                }
                cur.left = root.left;
                root = root.right;
                return root;
            }
        }
        if(root.val < key) root.right = deleteNode(root.right,key);
        if(root.val > key) root.left  = deleteNode(root.left,key);
        return root;
    }
}

共小伙伴们参考还有其他的代码，我也拉一下，不过差别不大，思路都是一样的，只是写法有点细微的区别：

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        root = delete(root,key);
        return root;
    }
    public TreeNode delete(TreeNode root, int key){
        if(root == null) return null;

        if(root.val > key){
            root.left = delete(root.left,key);
        }else if(root.val < key){
            root.right = delete(root.right,key);
        }else{
            if(root.left == null) return root.right;
            if(root.right == null) return root.left;
            TreeNode tmp = root.right;
            while(tmp.left != null){
                tmp = tmp.left;
            }
            root.val = tmp.val;
            root.right = delete(root.right,tmp.val);
        }
        return root;
    }
}