题目描述

给定一个二叉搜索树，同时给定最小边界 L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在 [L, R] 中 (R>=L)。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

样例

输入: 
    1
   / \
  0   2

  L = 1
  R = 2

输出: 
    1
      \
       2

输入: 
    3
   / \
  0   4
   \
    2
   /
  1

  L = 1
  R = 3

输出: 
      3
     / 
   2   
  /
 1

算法

(递归) $O(n)$

1. 由于这是一颗二叉搜索树，我们可以根据当前结点的值，或将当前结点及其右子树砍掉，或将当前结点及其左子树砍掉，或保留当前结点。
2. 所以可以使用递归，如果当前结点为空，则直接返回空。
3. 如果当前结点的值小于 L，则返回递归右子树的结果。
4. 如果当前结点的值大于 R，则返回递归左子树的结果。
5. 否则当前结点的左子树赋值为递归左子树的结果，右子树赋值为递归右子树的结果。

时间复杂度

• 每个结点最多遍历一次，故时间复杂度为 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (!root)
            return root;
        if (root -> val < L)
            return trimBST(root -> right, L, R);
        else if (root -> val > R)
            return trimBST(root -> left, L, R);
        root -> left = trimBST(root -> left, L, R);
        root -> right = trimBST(root -> right, L, R);
        return root;
    }
};