题目
给定一个二叉搜索树,同时给定最小边界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 = 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; } }
|