LeetCode669 修建二叉搜索树

链接: 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;
}
};