题目链接:450. 删除二叉搜索树中的节点
题目描述:
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
首先找到需要删除的节点;
如果找到了,删除它。
说明: 要求算法时间复杂度为 O(h),h 为树的高度。
样例:
root = [5,3,6,2,4,null,7]
key = 3
5
/ \
3 6
/ \ \
2 4 7
给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
5
/ \
4 6
/ \
2 7
另一个正确答案是 [5,2,6,null,4,null,7]。
5
/ \
2 6
\ \
4 7
解法一:官方题解
1、要删除的节点为叶子节点,可以直接删除。
2、要删除的几点不是叶子节点且拥有右节点,则该节点可以由该节点的后继节点进行替代,该后继节点位于右子树中较低的位置。然后可以从后继节点的位置递归向下操作以删除后继节点。(也就是说在删除的要节点的右子树中找一个最小的节点)
3、要删除的节点不是叶子节点,且没有右节点但是有左节点。这意味着它的后继节点在它的上面,但是我们并不想返回。我们可以使用它的前驱节点进行替代,然后再递归的向下删除前驱节点。(也就是在要删除的节点左子树中找最大的节点)
算法描述:
代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int successor(TreeNode root){ //要删除的结点无左子树,但有右子树,找当前结点的后继结点(也就是在右子树中找最小的结点代替)
root=root.right;
while(root.left!=null) root=root.left;
return root.val;
}
public int predecessor(TreeNode root){ //要删除的结点无右子树,但有左子树,找当前结点的前驱结点(也就是在左子树中找最大的结点代替)
root=root.left;
while(root.right!=null) root=root.right;
return root.val;
}
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null) return null;
if(root.val>key) root.left=deleteNode(root.left,key);
else if(root.val<key) root.right=deleteNode(root.right,key);
else{
if(root.left==null&&root.right==null) root=null;
else if(root.left!=null){ //要删除的结点有左子树
root.val=predecessor(root);
root.left=deleteNode(root.left,root.val);
}else{//要删除的结点无左子树
root.val=successor(root);
root.right=deleteNode(root.right,root.val);
}
}
return root;
}
}
解法二:
根据二叉搜索树的性质
1、如果目标节点大于当前节点值,则去右子树中删除;
2、如果目标节点小于当前节点值,则去左子树中删除;
3、如果目标节点就是当前节点,分为以下三种情况:
- 其无左子节点:其右子顶替其位置,删除了该节点;
- 其无右子:其左子顶替其位置,删除了该节点;
- 其左右子节点都有:其左子树转移到其右子树的最左节点的左子树上,然后右子树顶替其位置,由此删除了该节点。
代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null) return null;
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;
if(root.right==null) return root.left;
TreeNode node=root.right;//要删除节点左右子节点都有
while(node.left!=null){//寻找欲删除节点右子树的最左节点
node=node.left;
}
node.left=root.left;//将欲删除节点的左子树成为其右子树的最左节点的左子树
root=root.right;// 欲删除节点的右子节点顶替其位置,节点被删除
}
return root;
}
}