删除结点的算法如下:
- 如果目标节点大于当前节点值,则去右子树中删除;
- 如果目标节点小于当前节点值,则去左子树中删除;
- 如果目标节点就是当前节点,分为以下三种情况:
(1)左子树为空:其右子顶替其位置,删除了该节点;
(2)右子树为空:其左子顶替其位置,删除了该节点;
(3)左右子树均不为空:其左子树转移到其右子树的最左节点的左子树上,然后右子树顶替其位置,即删除该节点。
实现代码如下:
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null) return null;
if(key>root.val) {
root.right=deleteNode(root.right,key);
}
else if(key<root.val) {
root.left=deleteNode(root.left,key);
}
else {
//当前结点就是要删除的结点
if(root.left==null) return root.right;
else if(root.right==null) return root.left;
else {
TreeNode node=root.right;
while(node.left!=null) {
node=node.left;//寻找删除结点右子树的最左边叶子
}
node.left=root.left;//把要删除结点的左子树接到node的左子树
root=root.right;//要删除结点的右儿子成为根
}
}
return root;
}
}