题目描述
给定一棵具有不同节点值的二叉查找树，删除树中与给定值相同的节点。如果树中没有相同值的节点，就不做任何处理。你应该保证处理之后的树仍是二叉查找树。
思路
递归。
找不到，返回null
找到了，分两种情况：
1、如果节点的left或right为null，返回那个不为null的，如果都为null，返回null
2、如果节点的left或right都不为null，将left的right节点加到right的左子树的最后一个node的left处，返回left
代码
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
| public TreeNode removeNode(TreeNode root, int value) {
// write your code here
if(root == null) {
return null;
}
if(value > root.val) {
root.right = removeNode(root.right, value);
return root;
}else if(value < root.val) {
root.left = removeNode(root.left, value);
return root;
}else {
if(root.left == null || root.right == null) {
if(root.left == null) {
return root.right;
}else {
return root.left;
}
}else {
TreeNode tmp = root.right;
while(tmp.left != null) {
tmp = tmp.left;
}
tmp.left = root.left.right;
root.left.right = root.right;
return root.left;
}
}
}
|
考差点