java数据结构与算法刷题-----LeetCode450. 删除二叉搜索树中的节点
- 如果当前结点node是要删除的结点,我们可以选择以下两种方案任意一种
- 右子树成为当前新的node。并将左子树插入右子树中
- 左子树成为新的node,并将右子树插入左子树中。
- 我们这里选择,提上来右子树,然后按照BST的规则,将左子树插入到提上来的右子树中
1. 递归
class Solution {
public TreeNode deleteNode(TreeNode root,int key){
if(root == null) return null;
if(key < root.val){
root.left = deleteNode(root.left,key);
return root;
}else if(key > root.val){
root.right = deleteNode(root.right,key);
return root;
}
if(key == root.val) return insertBST(root.right,root.left);
return root;
}
public TreeNode insertBST(TreeNode root,TreeNode node){
if(root == null) return node;
if(node == null) return root;
if(root.val < node.val){
if(root.right == null) root.right = node;
else insertBST(root.right,node);
}else if(root.val > node.val){
if(root.left == null) root.left = node;
else insertBST(root.left,node);
}
return root;
}
}
2. 迭代
class Solution {
public TreeNode deleteNode(TreeNode root,int key){
if(root == null) return null;
TreeNode cur = root,curParent = null;
while(cur != null && cur.val!=key){
curParent = cur;
if(key < cur.val) cur = cur.left;
else if(key > cur.val) cur = cur.right;
}
if(cur == null) return root;
cur = insertBST(cur.right,cur.left);
if(curParent == null)return cur;
if(curParent.left!=null&&curParent.left.val == key) curParent.left = cur;
else if(curParent.right != null && curParent.right.val == key) curParent.right = cur;
return root;
}
public TreeNode insertBST(TreeNode root,TreeNode node){
if(root == null && node == null) return null;
else if(root == null) return node;
else if(node == null) return root;
TreeNode cur = root;
while(cur != null){
if(node.val < cur.val) {
if(cur.left == null) {
cur.left = node;break;
}
else cur = cur.left;
}else if(node.val > cur.val){
if(cur.right == null) {cur.right = node;break;}
else cur = cur.right;
}
}
return root;
}
}
原文地址:https://blog.csdn.net/grd_java/article/details/136306114
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!