For this question, we should first consider how does deletion in binary tree works in an inorder traversal:
1. if the node to be deleted is a leaf node, just delete it (set it to null)
2. if the node has a successor node, replace the node value with the successor value, and delete the successor. which means, the replace the successor's value with its successor's value and so on(recursion here)
3. if the node has a predecessor node, do the same as the successor, this time, all successor = predecessor.
Then we can consider for each node, what procedure we should take during recursion:
1. just like normal recursion traversal, if root == null, return null
2. root.left = recursion(root.left);
3. deal with the current node value:
if cur == key, it is the node to be deleted
i. if it's a leaf node, return null
ii. if it has successor, cur.val = successor.value; cur.right = recursion(cur.right, successor), return cur;
iii. else if it has predecessor, cur.val = predecessor.value; cur.left = recurtion(cur.left,predecessor) return cur;
4. root.right = recursion(root.right);
5. return root;
how to find the predecessor and successor in an inorder?
predecessor: the rightmost of the node's left
successor: the leftmost of the node's right
Code：
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null) return null;
root.left = deleteNode(root.left, key);
if(root.val == key){
if(root.left == null && root.right == null){
return null;
}
if(root.right!=null){
TreeNode s = successor(root);
root.val = s.val;
root.right = deleteNode(root.right,s.val);
return root;
} else if (root.left !=null){
TreeNode s = predecessor(root);
root.val = s.val;
root.left = deleteNode(root.left,s.val);
return root;
}
}
root.right = deleteNode(root.right, key);
return root;
}
public TreeNode predecessor(TreeNode root){
root = root.left;
while(root.right !=null){
root = root.right;
}
return root;
}
public TreeNode successor(TreeNode root){
root = root.right;
while(root.left !=null){
root = root.left;
}
return root;
}
