|
2 | 2 |
|
3 | 3 | importcom.fishercoder.common.classes.TreeNode; |
4 | 4 |
|
| 5 | +importjava.util.ArrayList; |
| 6 | +importjava.util.List; |
| 7 | + |
5 | 8 | publicclass_450 { |
6 | 9 | publicstaticclassSolution1 { |
7 | | - |
8 | 10 | /** |
9 | 11 | * credit: https://discuss.leetcode.com/topic/65792/recursive-easy-to-understand-java-solution |
10 | 12 | * Steps: |
@@ -45,4 +47,101 @@ private TreeNode getMin(TreeNode node) { |
45 | 47 | } |
46 | 48 | } |
47 | 49 |
|
| 50 | +publicstaticclassSolution2 { |
| 51 | +/** |
| 52 | + * My original, but brute force solution, time complexity: O(n) instead of O(h) |
| 53 | + */ |
| 54 | +publicTreeNodedeleteNode(TreeNoderoot,intkey) { |
| 55 | +List<Integer>list =newArrayList<>(); |
| 56 | +dfs(root,key,list); |
| 57 | +returnformBst(list,0,list.size() -1); |
| 58 | + } |
| 59 | + |
| 60 | +privateTreeNodeformBst(List<Integer>list,intleft,intright) { |
| 61 | +if (left >right) { |
| 62 | +returnnull; |
| 63 | + } |
| 64 | +intmid =left + (right -left) /2; |
| 65 | +TreeNoderoot =newTreeNode(list.get(mid)); |
| 66 | +root.left =formBst(list,left,mid -1); |
| 67 | +root.right =formBst(list,mid +1,right); |
| 68 | +returnroot; |
| 69 | + } |
| 70 | + |
| 71 | +privateList<Integer>dfs(TreeNoderoot,intkey,List<Integer>list) { |
| 72 | +if (root ==null) { |
| 73 | +returnlist; |
| 74 | + } |
| 75 | +dfs(root.left,key,list); |
| 76 | +if (root.val !=key) { |
| 77 | +list.add(root.val); |
| 78 | + } |
| 79 | +dfs(root.right,key,list); |
| 80 | +returnlist; |
| 81 | + } |
| 82 | + } |
| 83 | + |
| 84 | +publicstaticclassSolution3 { |
| 85 | +/** |
| 86 | + * credit: https://leetcode.com/problems/delete-node-in-a-bst/solution/ |
| 87 | + * |
| 88 | + * Again, using a pen and paper to visualize helps a lot. |
| 89 | + * Putting a BST into an inorder traversal array helps a lot to understand: |
| 90 | + * |
| 91 | + * The successor of a node is always: go the right once, and then go to the left as many times as possible， |
| 92 | + * because the successor is the next smallest element that is larger than the current one: so going to the right one time |
| 93 | + * makes sure that we are finding the larger one, and then keeping going to the left makes sure that we'll find the smallest one. |
| 94 | + * |
| 95 | + * The predecessor of a node is always: go the left once, and then go the right as many times as possible, |
| 96 | + * because the predecessor is the largest element that is smaller than the current one: so going to the left once makes it smaller than the current node, |
| 97 | + * then keeping going to the right makes sure that we are getting the largest element. |
| 98 | + */ |
| 99 | +publicTreeNodedeleteNode(TreeNoderoot,intkey) { |
| 100 | +if (root ==null) { |
| 101 | +returnnull; |
| 102 | + } |
| 103 | +if (root.val <key) { |
| 104 | +//delete from the right subtree |
| 105 | +root.right =deleteNode(root.right,key); |
| 106 | + }elseif (root.val >key) { |
| 107 | +//delete from the left subtree |
| 108 | +root.left =deleteNode(root.left,key); |
| 109 | + }else { |
| 110 | +//delete this current node, three cases: |
| 111 | +if (root.left ==null &&root.right ==null) { |
| 112 | +//case 1: if this is a leaf |
| 113 | +root =null; |
| 114 | + }elseif (root.right !=null) { |
| 115 | +//case 2: has a right child, regardless whether it has left children or not, |
| 116 | +//this is because we want to traverse the tree only once, so we'll want to keep going down the tree |
| 117 | +root.val =findSuccessor(root);//we find the value of the successor and assign it to current root.val |
| 118 | +root.right =deleteNode(root.right,root.val);//and then we delete this successor's value in the right subtree as it's been moved up |
| 119 | + }elseif (root.left !=null) { |
| 120 | +//case 3: this node is not a leaf and no right child, but has a left child |
| 121 | +//That means that its successor is somewhere upper in the tree but we don't want to go back. |
| 122 | +//Let's use the predecessor here which is somewhere lower in the left subtree. |
| 123 | +root.val =findPredecessor(root); |
| 124 | +root.left =deleteNode(root.left,root.val); |
| 125 | + } |
| 126 | + } |
| 127 | +returnroot; |
| 128 | + } |
| 129 | + |
| 130 | +privateintfindPredecessor(TreeNoderoot) { |
| 131 | +root =root.left; |
| 132 | +while (root.right !=null) { |
| 133 | +root =root.right; |
| 134 | + } |
| 135 | +returnroot.val; |
| 136 | + } |
| 137 | + |
| 138 | +privateintfindSuccessor(TreeNoderoot) { |
| 139 | +root =root.right; |
| 140 | +while (root.left !=null) { |
| 141 | +root =root.left; |
| 142 | + } |
| 143 | +returnroot.val; |
| 144 | + } |
| 145 | + } |
| 146 | + |
48 | 147 | } |