主題
題目連結：
題目意譯：
給定一棵二元搜尋樹（Binary Search Tree，BST）的根節點之參考（reference）root 以及一個鍵值 key，將 BST 中有著 key 作為節點值的節點刪除。回傳刪除後的 BST 的根節點之參考（可能會被更新）。
基本上，刪除這個行為可以被分成兩個階段：
搜尋需要刪除的節點。
如果有找到這樣子的節點，刪除該節點。
限制：
樹中的節點數位於範圍 [0, 10 ^ 4] 中。
-10 ^ 5 ≦ Node.val ≦ 10 ^ 5
每個節點有著獨一無二的數值。
root 為一個合法的二元搜尋樹。
-10 ^ 5 ≦ key ≦ 10 ^ 5
進階：你可以在時間複雜度 O(樹高) 內解出嗎？
範例測資：
範例 1：
輸入： root = [5,3,6,2,4,null,7], key = 3
輸出： [5,4,6,2,null,null,7]
解釋： 給定要刪除的鍵值 3。因此我們需要找到節點值為 3 的節點並刪除。
其中一個合法的答案為 [5,4,6,2,null,null,7]，顯示於上圖。
請注意到另一個合法的答案為 [5,2,6,null,4,null,7] 且這同樣也會接受。
範例 2：
輸入： root = [5,3,6,2,4,null,7], key = 0
輸出： [5,3,6,2,4,null,7]
解釋： 樹中並不包含節點值 = 0 的節點。
範例 3：
輸入： root = [], key = 0
輸出： []
解題思維：
首先，先找找看有沒有節點值為 key 的節點，作法如這題。
如果沒找到這樣的節點當然就沒事，整個樹將維持原樣，因此直接回傳原本的參考 root 即可；問題是如果找到了，拔掉找到的那個節點（以下稱其為 X）要怎麼更新這棵樹？
我們可以把 X 有沒左右子樹的情況分成四種：
一：X 沒有左子樹，也沒有右子樹。此時直接把 X 刪除即可，至於 X 的父母節點（如果有的話），則會把原本指向 X 的指標設為空指標；
二：X 沒有左子樹，但有著右子樹。此時把右子樹的根節點取代 X 的位置即可。
三：X 有著左子樹，但沒有右子樹。類似二，把左子樹取代 X 的位置即可。
四：X 有著左子樹，也有著右子樹。此時比較麻煩。為了符合刪除 X 之後依舊符合 BST 的定義，我們需要在左子樹中找到其中的最大值或是右子樹中的最小值。假設我們找得是前者，則可以看到該最大值將會是在左子樹的根節點一直往右走到底即可（根據 BST 的定義）。此時我們將其數值取代 X 的數值，然後刪掉這個節點即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
