脚本宝典收集整理的这篇文章主要介绍了[LintCode] Remove Node in Binary Search Tree [理解BST],脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
PRoblem
Given a root of Binary SeArch Tree wITh unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.
Example
Given binary search tree:
5
/
3 6
/
2 4
Remove 3, you can either return:
5
/
2 6
4
or
5
/
4 6
/
2
@H_406_69@Note
以下是rebuild的示意:先让r
到达r
的最左端,然后将l
接在r
的左子树,这样就把所有比root.left
大的结点都集合在root.right
了。将root.right
接在root.left
的右子树,然后返回root.left
即可。
(1)
root
/
left right
/ /
x l r x
(2)
left right
/ /
x r x
/
l
(3)
left
/
x right
/
r x
/
l
Solution
public class Solution {
public TreeNode removeNode(TreeNode root, int value) {
TreeNode dummy = new TreeNode (-1), pre = dummy, cur = root;
dummy.right = root;
while (cur != null) {
if (cur.val == value) {
if(pre.left == cur) {
pre.left = makenew(cur);
}
else pre.right = makenew(cur);
break;
}
else if (cur.val < value) {
pre = cur;
cur = cur.right;
}
else {
pre = cur;
cur = cur.left;
}
}
return dummy.right;
}
private TreeNode makenew(TreeNode node) {
if (node.left == null || node.right == null) {
return node.left == null ? node.right : node.left;
}
TreeNode left = node.left.right;
TreeNode right = node.right.left;
while (right.left != null) {
right = right.left;
}
right.left = left;
node.left.right = node.right;
return node.left;
}
}
以上是脚本宝典为你收集整理的[LintCode] Remove Node in Binary Search Tree [理解BST]全部内容,希望文章能够帮你解决[LintCode] Remove Node in Binary Search Tree [理解BST]所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。