1. question: 修剪二叉搜索树（中等）
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trim-a-binary-search-tree
示例 1：
1
2
| 输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
|
示例 2：
1
2
| 输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]
|
提示：
1
2
3
4
5
| 树中节点数在范围 [1, 104] 内
0 <= Node.val <= 104
树中每个节点的值都是 唯一 的
题目数据保证输入是一棵有效的二叉搜索树
0 <= low <= high <= 104
|
2. answers
这道题和删除二叉搜索树中的节点类似，只不过上道题是只删除一个节点，需要重构。而这道题删除的是区间，因为二叉搜索树的节点之间有大小关系，所以如果某个节点不满足要求，那么它的左子树或者右子树也一定不满足要求。
- 如果节点小于区间，那么该节点的左子树也一定不满足要求。此时将该节点以及左子树删除，保留其右子树。即右子树的根节点代替当前节点。
- 如果节点大于区间，那么该节点的右子树也一定不满足要求。此时将该节点以及右子树删除，保留其左子树。即左子树的根节点代替当前节点。
因此，在遍历的时候，仍然需要保留当前节点的父节点。注意删除当前节点后，当前节点的变化，以及当前节点的父节点变化。先序迭代的代码如下所示：
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
| public class Solution_0075 {
public TreeNode trimBST(TreeNode root, int low, int high) {
TreeNode head = new TreeNode(root.val, null, root);
root = head;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = head;
while(root != null || stack.size() > 0) {
if(root == null) {
root = stack.pop();
pre = stack.pop();
}
if(root.right != null) {
stack.push(root);
stack.push(root.right);
}
if(root.val < low) {
if(pre.left == root) pre.left = root.right;
if(pre.right == root) pre.right = root.right;
root = root.right;
} else if(root.val > high) {
if(pre.left == root) pre.left = root.left;
if(pre.right == root) pre.right = root.left;
root = root.left;
}
else {
pre = root;
root = root.left;
}
}
return head.right;
}
public static void main(String[] args) {
TreeNode tn4 = new TreeNode(2);
TreeNode tn3 = new TreeNode(4);
TreeNode tn2 = new TreeNode(1, null, tn4);
TreeNode tn1 = new TreeNode(3, tn2, tn3);
Solution_0075 s = new Solution_0075();
TreeNode result = s.trimBST(tn1, 3, 4);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(result);
while(queue.size() > 0 ) {
int length = queue.size();
while(length-- > 0) {
result = queue.poll();
System.out.print(result.val + "\t");
if(result.left != null) queue.offer(result.left);
if(result.right != null) queue.offer(result.right);
}
System.out.println();
}
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
