題目描述：

給定一個二叉搜索樹的根節(jié)點 root 和一個值 key，刪除二叉搜索樹中的 key 對應(yīng)的節(jié)點，并保證二叉搜索樹的性質(zhì)不變。返回二叉搜索樹（有可能被更新）的根節(jié)點的引用。

一般來說，刪除節(jié)點可分為兩個步驟：

首先找到需要刪除的節(jié)點；
如果找到了，刪除它。
說明： 要求算法時間復(fù)雜度為 O(h)，h 為樹的高度。

示例:

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

5

/
3 6
/ \
2 4 7

給定需要刪除的節(jié)點值是 3，所以我們首先找到 3 這個節(jié)點，然后刪除它。

一個正確的答案是 [5,4,6,2,null,null,7], 如下圖所示。

5

/
4 6
/
2 7

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

5

/
2 6
\
4 7

題目鏈接

難度：中等

思路：

找到需要刪除的節(jié)點，可以使用前驅(qū)節(jié)點或者后繼節(jié)點代替被刪除的節(jié)點，這里我使用的是后繼節(jié)點，找到刪除節(jié)點中的最小值得節(jié)點，與需要刪除的節(jié)點替換即可。
思路很快就想出來了，但是由于對 二叉樹的操作不是很熟悉，導(dǎo)致花了一個小時也沒有完全解出來，部分測試用例還是不能通過，無奈只得看參考。。
找了個和我思路差不多的代碼，學(xué)習(xí)他人并修改自己的代碼。

代碼：

/**
 * 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;
        }
        //替換后繼節(jié)點
        if (curr != null) {
            //左右子節(jié)點均不為空，找出后繼節(jié)點和當前節(jié)點替換
            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;
                //轉(zhuǎn)換為
                curr = successor;
            }
            // 然后將后繼結(jié)點作為目標結(jié)點(因為后繼結(jié)點沒有左子樹，
            // 所以問題轉(zhuǎn)化為刪除有一個子結(jié)點或沒有子結(jié)點的結(jié)點的問題)
            TreeNode child = curr.left == null ? curr.right : curr.left;
            //根節(jié)點為要刪除的節(jié)點
            if (parent == null) {
                return child;
            }else {
                if (parent.left == curr) {
                    parent.left = child;
                } else {
                    parent.right = child;
                }
            }
            //這一步，我還有所欠缺，curr置空，交給gc回收
            curr = null;
        }
        return root;
    }
}

總結(jié)：

練習(xí)多了之后，思路已經(jīng)有一點了，但是將思路變?yōu)榇a，這一步還是有所欠缺！代碼質(zhì)量也有待提高，之前按照自己的思路寫出來的代碼，邏輯很復(fù)雜，改為這種之后一目了然。。。我好菜T____T。加油?。?！