LeetCode669 修剪二叉搜索树

发表于 | 分类于 |
字数统计: 394 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/trim-a-binary-search-tree

题意

给定一个二叉查找树和两个整数 L 和 R，且 L < R，试修剪此二叉查找树，使得修剪后所有节点的值都在 [L, R] 的范围内

解法

递归确实是个很神奇的算法，用子问题去解决原问题
子问题是和原问题相似，规模变小的一个问题
子问题解决了，原问题也就解决了
打开思路以后，其实就会发现，root可能会在范围内，也有可能不在，讨论一下：

  1. 如果在范围内，那么说明root是要保留的，也就是说不用处理root，处理左右子树就可以了。
  2. 如果不再范围内，假如root-val > low，且根据BST性质，就会发现，左子树和root都在区间外，要保留的只可能是处理后的右子树。
  3. 反之，如果root->val > high，需要保留的只有处理后的左子树

所以，做这种题，就是先考虑：

  1. 是否能用题目的定义
  2. 如果可以用，那么是否可以用题目定义处理子问题（子树）
  3. 如果可以处理子问题，是否可以用子问题结果凑出原定义

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(!root) return nullptr;
        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;
    }
};