二叉树

题目

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