450.?Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.

If the node is found, delete the node.

Note:?Time complexity should be O(height of tree).

首先找該節(jié)點(diǎn)，然后刪除。注意的是，對(duì)于刪除這類(lèi)操作，要保留父節(jié)點(diǎn)

刪除：以被刪除元素為父節(jié)點(diǎn)的子樹(shù)，刪除其父節(jié)點(diǎn)。如果父節(jié)點(diǎn)下左右子樹(shù)都存在，則選擇左子樹(shù)（可以任意選擇一個(gè)）,選擇左子樹(shù)中最大的點(diǎn)。這個(gè)點(diǎn)可能是左子樹(shù)的根節(jié)點(diǎn)，一定是最右的節(jié)點(diǎn)。

找到該節(jié)點(diǎn)，將其值賦給父節(jié)點(diǎn)。然后刪除改節(jié)點(diǎn)。則若是子樹(shù)的父節(jié)點(diǎn)，則子樹(shù)的左子樹(shù)為根節(jié)點(diǎn)的左子樹(shù)，否則左子樹(shù)作為被刪除節(jié)點(diǎn)父節(jié)點(diǎn)的右子樹(shù)。代替被刪除節(jié)點(diǎn)原來(lái)的位置

注意，最后一步，是要將左子樹(shù)賦值，不是空指針。