87. Remove Node from a Binary Search Tree

Leave a comment

September 17, 2016 by oneOokay

我要疯了,今天大拇指的指甲油涂好了被弄坏涂好了又被弄坏再涂又又被弄坏了,卸了涂涂了卸三次!

binary search tree: 概念都要忘光了=。=

a node is LARGER than all the left elements and SMALLER than all the right elements

这个主要包含两部分,一是找到要删除的node,二是将node删除。找到要删除的node:其实是要找到要被删除的node的parent,这个便于接下来的删除操作。

删除:

九章的解法(挺好的,以后用这个解法吧):

public TreeNode removeNode(TreeNode root, int value) {
TreeNode dummy = new TreeNode(0);
dummy.left = root;
TreeNode parent = findParentNode(dummy, root, value);
TreeNode node;
if (parent.left != null && parent.left.val == value) {
node = parent.left;
}else if (parent.right != null && parent.right.val == value) {
node = parent.right;
}else {
return root;
}
deleteNode(parent, node);
return dummy.left;
}

private TreeNode findParentNode(TreeNode parent, TreeNode node, int value){
if(node == null) { //不要忘了node为null的情况
return parent;
}
if(node.val == value) {
return parent;
}
if (node.val > value) {
return findParentNode(node, node.left, value);
}else {
return findParentNode(node, node.right, value);
}}

private void deleteNode(TreeNode parent, TreeNode node){
if (node.right == null) {//参照我的解法的注释
if (parent.left == node) {
parent.left = node.left;
}else {
parent.right = node.left;
}
}else {
TreeNode temp = node.right;
TreeNode father = node;
while (temp.left != null) { //loop循环找到node右子树的最左叶子temp
father = temp;
temp = temp.left;
}

if (father.left == temp) {//因为temp为node有字数的最左叶子,是要被拿走的,所以接下来处理把temp拿走以后(相当于一个delete操作其实)temp的右子树直接连到temp的father;跟上面的当node的右子树为null的情况其实是一样的。
father.left = temp.right;
}else {
father.right = temp.right;
}
//接下来把 temp放到node的位置
if (parent.left == node) {
parent.left = temp;
}else {
parent.right = temp;
}
//把temp与node左右子树相连接,结束。
temp.left = node.left;
temp.right = node.right;
}}

我的解法:

public TreeNode removeNode(TreeNode root, int value) {
TreeNode dummy = new TreeNode(0);
dummy.left = root; //dummy node 可以完美处理root node被删掉的情况

TreeNode parent = findNode(dummy, root, value); //找到删除目标node的parent,所以这里需要传入一个parent node和node
TreeNode node;

//以下来找到删除目标node,node可能是parent的左儿子也可能是parent的右儿子,也可能parent根本没有儿子,此时表示,没有找到删除目标node。
if (parent.left != null && parent.left.val == value) {
node = parent.left;
}else if (parent.right != null && parent.right.val == value) {
node = parent.right;
}else {
return root;
}
deleteNode(parent, node); //进行删除node
return dummy.left;
}
private TreeNode findNode(TreeNode parent, TreeNode node, int value) {
if(node == null) {
return parent;
}
if(node.val == value){
return parent;
}
if (value < node.val) {
return findNode(node, node.left, value);
}else {
return findNode(node, node.right, value);
}
}

private void deleteNode(TreeNode parent, TreeNode node){
if (node.right == null) { //如果node并没有右子树
if (parent.left == node) { //被删除的node为parent的左儿子,那么node的左子树都小于node,所以也会小于parent,node的左儿子赋给parent.left,符合BST。
parent.left = node.left;
}else { //被删除的node为parent的右儿子,那么node大于parent,且node的左子树的所有元素都会大于parent,所以把node的左儿子赋给parent的右儿子,符合BST。
parent.right = node.left;
}
}else { //node有右子树,可能有也可能没有左子树
//无论被删除的是parent的左儿子还是右儿子,都把删除目标node的右儿子放到node的位置。

if (parent.left == node) {
parent.left = node.right;
}else {
parent.right = node.right;
}

TreeNode temp = node.right; //把右子树暂存起来

//以下的loop找到node的右子树的最左leave。如果node右子树并没有左儿子,那么temp就会为node的右儿子本身。
TreeNode father = node.right;
while (temp.left != null) {
father = temp;
temp = temp.left;
}
temp.left = node.left; //node的左子树赋给node右子树的最左叶子。结束。
}}

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: