669. 修剪二叉搜索樹

思路

程式碼

遞迴

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);
        }     
        // low <= root->val <= high
        // 當前節點合法，左右子樹不一定
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(H)$, $H$為樹的高度