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

题目描述：

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

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

首先找到需要删除的节点；
如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

示例:

root = [5,3,6,2,4,null,7]
key = 3

5

/
3 6
/ \
2 4 7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

5

/
4 6
/
2 7

另一个正确答案是 [5,2,6,null,4,null,7]。

5

/
2 6
\
4 7

题目链接

难度：中等

思路：

找到需要删除的节点，可以使用前驱节点或者后继节点代替被删除的节点，这里我使用的是后继节点，找到删除节点中的最小值得节点，与需要删除的节点替换即可。
思路很快就想出来了，但是由于对 二叉树的操作不是很熟悉，导致花了一个小时也没有完全解出来，部分测试用例还是不能通过，无奈只得看参考。。
找了个和我思路差不多的代码，学习他人并修改自己的代码。

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode parent = null;

        TreeNode curr =  root;
        //找key
        while(curr != null && curr.val != key) {
            parent = curr;
            curr = curr.val > key ? curr.left :  curr.right;
        }
        //替换后继节点
        if (curr != null) {
            //左右子节点均不为空，找出后继节点和当前节点替换
            if (curr.right != null && curr.left != null) {
                parent = curr;
                TreeNode successor = curr.right;
                while(successor.left != null) {
                    parent = successor;
                    successor = successor.left;
                }
                curr.val = successor.val;
                //转换为
                curr = successor;
            }
            // 然后将后继结点作为目标结点(因为后继结点没有左子树，
            // 所以问题转化为删除有一个子结点或没有子结点的结点的问题)
            TreeNode child = curr.left == null ? curr.right : curr.left;
            //根节点为要删除的节点
            if (parent == null) {
                return child;
            }else {
                if (parent.left == curr) {
                    parent.left = child;
                } else {
                    parent.right = child;
                }
            }
            //这一步，我还有所欠缺，curr置空，交给gc回收
            curr = null;
        }
        return root;
    }
}

总结：

练习多了之后，思路已经有一点了，但是将思路变为代码，这一步还是有所欠缺！代码质量也有待提高，之前按照自己的思路写出来的代码，逻辑很复杂，改为这种之后一目了然。。。我好菜T____T。加油！！！