1 解题思想
现在有一个二叉搜索树,现在要让你删除一个节点,并且保证整个BST的性质不变。
要保证整个性质,我们必须在删除的位置上,找一个合适的值来进行替换,使得BST上的每个节点都满足 当前节点的值大于左节点但是小于右节点
而替换策略就是: 1、当前删除位置,用左边子树的最大值的节点替换 2、或者是,用右边子树的最小值的节点替换
用上面的策略就可以保证删除后性质不变,并且调整开销也很少
2 原题
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
3 AC解
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int findReplacement(TreeNode parent,TreeNode node,
boolean isLeft){
if(node.right ==
null){
if (isLeft)
parent.left = node.left;
else parent.right = node.left;
return node.val;
}
return findReplacement(node,node.right,
false);
}
public TreeNode
deleteNode(TreeNode root,
int key) {
if(root==
null)
return null;
if(root.val == key){
if(root.left ==
null)
return root.right;
if(root.right ==
null)
return root.left;
root.val = findReplacement(root,root.left,
true);
}
else{
if(root.val > key)
root.left = deleteNode(root.left,key);
else
root.right = deleteNode(root.right,key);
}
return root;
}
}
转载请注明原文地址: https://ju.6miu.com/read-600007.html