少女祈祷中...

题目

给定一个二叉搜索树,同时给定最小边界low和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high](high>=low) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。

示例1

  • 输入:root = [1,0,2], low = 1, high = 2
  • 输出:[1,null,2]
    修剪二叉树

示例2

  • 输入:root = [3,0,4,null,2,null,null,1], low = 1, high = 3
  • 输出:[3,2,null,1]
    修剪二叉树

《代码随想录》算法视频公开课

力扣题目链接

思路

  • 题目所给二叉树为搜索二叉树
  • 首先判断根结点是否在给定范围内,如果大于给定范围,则返回其根结点的左结点作为输出树的根结点,如果小于给定范围,则返回根结点的右结点作为根结点
  • 记录当前根结点,先向左树进行遍历剪切
  • 再次记录根结点,向右树进行遍历剪切

代码实现

迭代法

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
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root == null) return root;
//首先对根结点进行判断--是否超越给定边界
while(root != null && (root.val < low || root.val > high)){
//小于则返回根结点的右结点作为边界
if(root.val < low) root = root.right;
//反则返回根结点的左结点
else root = root.left;
}
//记录当前根结点,用于下述的遍历
TreeNode cur = root;
//遍历左树,寻找是否有需要剪切的结点
while(cur != null){
while(cur.left != null && cur.left.val < low){
//进行剪切操作,因为当cur.left.val小于边界时,其左子树全部小于,直接全切了,右树同样操作
cur.left = cur.left.right;
}
cur = cur.left;
}
cur = root;
while(cur != null){
while(cur.right != null && cur.right.val > high){
cur.right = cur.right.left;
}
cur = cur.right;
}

return root;

}
}