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).
Example:
root = [5,3,6,2,4,null,7]
key = 3
5
/ \
3 6
/ \ \
2 4 7
Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
5
/ \
4 6
/ \
2 7
Another valid answer is [5,2,6,null,4,null,7].
5
/ \
2 6
\ \
4 7
方法
记住BST树的特性，使用递归的方式进行查找，注意：当删除节点存在左子树和右子树时，找右子树的最左节点，将其值作为删除节点的新值，之后再递归删除删除节点的右子树中与删除节点相等的值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null){
return root;
}
if(root.val < key){
root.right = deleteNode(root.right,key);
}else if(root.val > key){
root.left = deleteNode(root.left,key);
}else{
if(root.left == null){
return root.right;
}else if(root.right == null){
return root.left;
}else{
TreeNode temp = root.right;
TreeNode tn = getMin(temp);
root.val = tn.val;
root.right = deleteNode(root.right, root.val);
}
}
return root;
}
public TreeNode getMin(TreeNode tn){
while(tn.left != null){
tn = tn.left;
}
return tn;
}
}