669. 修剪二叉搜索树

Problem: 669. 修剪二叉搜索树

思路

这道题可以总结为两句话:

小于low的节点,左子树不要。
大于high的节点,右子树不要。

因为他是二叉搜索树,小于low,说明左子树都小于low。

因为他是二叉搜索树,大于high,说明右子树都大于high。

解题方法

描述你的解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == nullptr) 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;
    }
};