-
Notifications
You must be signed in to change notification settings - Fork 20
/
Remove Node in Binary Search Tree.java
executable file
·243 lines (189 loc) · 7.03 KB
/
Remove Node in Binary Search Tree.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
H
tags: BST
方法1: Brutle一点。找到target和target的parent.
把target remove时,把target的children nodes 重新排列组成新的BST: inorder traversal, build tree based on inorder traversal list.
方法2: 分析规律,先找到target和parent, 然后根据性质,把target remove时,移动children nodes, 保证还是BST。
```
/*
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
Tags Expand
LintCode Copyright Binary Search Tree
*/
//Recap, 2024.2016
//Find target. Serialize (inorder) target's children. De-serialize the list, without target.
public class Solution {
public TreeNode removeNode(TreeNode root, int value) {
if (root == null) {
return root;
}
//Find target and target.parent
TreeNode parent = findTargetParent(root, value);
TreeNode target;
if (parent == null) {
return root;
}
if (parent.val == value) {
target = parent;
} else if (parent.left != null && parent.left.val == value) {
target = parent.left;
} else {
target = parent.right;
}
//Build inorder traversal based on target node.
ArrayList<TreeNode> list = new ArrayList<TreeNode>();
inorderTraversal(target, list, target);
//Build new subtree and attach to original tree
if (parent.val == value) {
return buildBFS(list, 0, list.size() - 1);
}
if (parent.left != null && parent.left.val == value) {
parent.left = buildBFS(list, 0, list.size() - 1);
} else {
parent.right = buildBFS(list, 0, list.size() - 1);
}
return root;
}
//Find and return target, where target.val == value
public TreeNode findTargetParent(TreeNode node, int value) {
if (node == null || node.val == value) {
return node;
}
if (value < node.val) {
if (node.left != null && value == node.left.val) {
return node;
}
return findTargetParent(node.left, value);
} else {
if (node.right != null && value == node.right.val) {
return node;
}
return findTargetParent(node.right, value);
}
}
//Traverse target's children and build a inorder list
public void inorderTraversal(TreeNode node, ArrayList<TreeNode> rst, TreeNode skipNode) {
if (node.left != null) {
inorderTraversal(node.left, rst, skipNode);
}
if (node.val != skipNode.val) {
rst.add(new TreeNode(node.val));
}
if (node.right != null) {
inorderTraversal(node.right, rst, skipNode);
}
}
//Build tree based on given inorder-traversal list
public TreeNode buildBFS(ArrayList<TreeNode> list, int start, int end) {
if (start < end) {
int mid = start + (end - start)/2;
TreeNode root = list.get(mid);
root.left = buildBFS(list, start, mid - 1);
root.right = buildBFS(list, mid + 1, end);
return root;
}
if (start == end) {
return list.get(start);
}
return null;
}
}
/*
Thoughts:
We can think of a couple different cases: where is that target node to remove? It can be root, a child (a couple more situations)
Note: before going futher, remember the technique to rip off parent node. In a binary tree, L > parent > R, so always find the L's right-most node and replace parent.
Cases1:
0. Root is target: find L's right-most node, replace root.
case1. A node with 2 null children: set target.parent.L/R = null
case2. A node with just just left node: set target.parent.L/R = target.right
case3. A node with left ndoe != null: find target.right-most node's left side X and replace target.parent.L/R.value = X.value. Remove set that X to null.
Divide into 2 major task:
1. Find the target node, and it's parent.
2. Remove that node (most complex logic)
*/
public class Solution {
public TreeNode removeNode(TreeNode root, int value) {
if (root == null || (root.left == null && root.right == null)) {
return null;
}
TreeNode dummy = new TreeNode(0);;
dummy.left = root;
//Find node
TreeNode parent = findTargetParent(dummy, root, value);
TreeNode child;
if (parent.left != null && parent.left.val == value) {
child = parent.left;
} else if (parent.right != null && parent.right.val == value) {
child = parent.right;
} else {
return dummy.left;
}
//Delete that node:
deleteTargetNode(parent, child);
return dummy.left;
}
//Find target node
public TreeNode findTargetParent(TreeNode parent, TreeNode node, int value){
if (node == null || node.val == value) {
return parent;
}
if (value < node.val) {
return findTargetParent(node, node.left, value);
} else {
return findTargetParent(node, node.right, value);
}
}
//Delete node
public void deleteTargetNode(TreeNode parent, TreeNode target) {
//Case1 + case2: (target.L == null && target.R == null) || (target.R == null && target.L != null)
if (target.right == null) {
if (parent.left == target) {
parent.left = target.left;
} else {
parent.right = target.left;
}
} else {//Case3: when target.right != null
TreeNode replaceNode = target.right;
TreeNode replaceParent = target;
while(replaceNode.left != null) {
replaceParent = replaceNode;
replaceNode = replaceNode.left;
}
//Remove replaceNode from replaceParent
if (replaceParent.left == replaceNode) {//Usually it'll be replaceParent.left
replaceParent.left = replaceNode.right;
} else {//Sometimes when target.left == null, than means replaceParent.right will be replaceNode (while loop didn't start at all)
replaceParent.right = replaceNode.right;
}
//Remove target from parent: not sure it's left or right node of parent
if (parent.left == target) {
parent.left = replaceNode;
} else {
parent.right = replaceNode;
}
replaceNode.left = target.left;
replaceNode.right = target.right;
}
}
}
```