二刷 05/2022
Version #1 Recursion
更改了TreeNode 的值，所以不是optimal
写了一个bug就是当root被删除的时候，代替root的点需要是左边的最大点或者右边的最小点，而不是简单的root.left或者root.right
反例
5
/ \
3 6
/ \ \
2 4 7
会变成
3
/ \
2 6
\ \
4 7
Time O(Height)
Space O(Height)
/**
* 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.left = deleteNode(root.left, key);
return root;
}
if (root.val < key) {
root.right = deleteNode(root.right, key);
return root;
}
if (root.left != null) {
TreeNode leftMax = root.left;
while (leftMax.right != null) {
leftMax = leftMax.right;
}
root.val = leftMax.val;
root.left = deleteNode(root.left, leftMax.val);
} else if (root.right != null) {
TreeNode rightMin = root.right;
while (rightMin.left != null) {
rightMin = rightMin.left;
}
root.val = rightMin.val;
root.right = deleteNode(root.right, rightMin.val);
} else {
root = null;
}
return root;
}
}
Version #2 Iteration
Runtime: 1 ms, faster than 12.04% of Java online submissions for Delete Node in a BST.
Memory Usage: 42.4 MB, less than 97.53% of Java online submissions for Delete Node in a BST.
/**
* 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) {
TreeNode curr = root;
TreeNode prev = null;
while (curr != null && curr.val != key) {
prev = curr;
if (curr.val > key) {
curr = curr.left;
} else {
curr = curr.right;
}
}
if (curr == null) { // target key not found
return root;
}
if (prev == null) {
return deleteRoot(curr);
}
if (prev.left == curr) {
prev.left = deleteRoot(curr);
} else {
prev.right = deleteRoot(curr);
}
return root;
}
private TreeNode deleteRoot(TreeNode root) {
System.out.println(root.val);
if (root == null || (root.left == null && root.right == null)) {
return null;
}
if (root.left == null) {
return root.right;
}
if (root.right == null) {
return root.left;
}
TreeNode rightMin = root.right;
TreeNode prev = root;
while (rightMin.left != null) {
prev = rightMin;
rightMin = rightMin.left;
}
if (prev != root) {
prev.left = rightMin.right;
rightMin.right = root.right;
}
rightMin.left = root.left;
return rightMin;
}
}
一刷
这道题感觉简直有一万个坑。。。
Version #1 Non-recursion Method
75.25 %
在deleteRoot的时候 要区分root.right是不是只有一个点
public class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root;
TreeNode curr = root;
TreeNode pre = null;
while (curr != null && curr.val != key) {
pre = curr;
if (curr.val > key) curr = curr.left;
else curr = curr.right;
}
if (pre == null) return deleteRoot(curr); //curr == root
if (pre.left == curr) pre.left = deleteRoot(curr);
else pre.right = deleteRoot(curr);
return root;
}
private TreeNode deleteRoot(TreeNode root) {
if (root == null) return root;
if (root.left == null) return root.right;
if (root.right == null) return root.left;
TreeNode rightMin = root.right;
TreeNode pre = root;
while (rightMin.left != null) {
pre = rightMin;
rightMin = rightMin.left;
}
if (pre != root) {
pre.left = rightMin.right;
rightMin.right = root.right;
}
rightMin.left = root.left;
return rightMin;
}
}
Version #2 Recursion
42.80 %
Definition: public TreeNode deleteNode(TreeNode root, int key)
Recursion之后的返回值 一定要和原来的root接起来！
“root.left = deleteNode(root.left, key)”
不接起来都白搭啊
这个方法感觉不是那么的elegant，因为不是换node而是换值
没有Iteration好，但是简单
public class Solution {
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) return root.right;
if (root.right == null) return root.left;
//TODO
TreeNode rightMin = findMin(root.right);
root.val = rightMin.val;
root.right = deleteNode(root.right, rightMin.val);
}
return root;
}
private TreeNode findMin(TreeNode root) {
while (root.left != null) root = root.left;
return root;
}
}
No comments:
Post a Comment