修剪二叉搜索树

题目链接

修剪二叉搜索树

题目描述

注意

• 二叉搜索树的性质： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
• 树中每个节点的值都是唯一的

解答思路

• 使用递归对每个节点进行遍历，对于某个节点，会有以下几种可能性：
  该节点的值小于规定的最小值，则只需要找其右节点是否符合即可
  该节点的值大于规定的最小值，则只需要找其左节点是否符合即可
  该节点的值符合规定的区间值，则需要对其左右节点都判断是否符合

代码

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) {
            return null;
        }
        if(root.val < low) {
            return trimBST(root.right, low, high);
        }
        if(root.val > high) {
            return trimBST(root.left, low, high);
        }
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

关键点

• 掌握递归的思想