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).
首先找该节点,然后删除。注意的是,对于删除这类操作,要保留父节点
删除:以被删除元素为父节点的子树,删除其父节点。如果父节点下左右子树都存在,则选择左子树(可以任意选择一个),选择左子树中最大的点。这个点可能是左子树的根节点,一定是最右的节点。
找到该节点,将其值赋给父节点。然后删除改节点。则若是子树的父节点,则子树的左子树为根节点的左子树,否则左子树作为被删除节点父节点的右子树。代替被删除节点原来的位置
注意,最后一步,是要将左子树赋值,不是空指针。