108. 정렬된 배열을 이진 탐색 트리로 변환

재귀적 접근

class Solution {
private:
    TreeNode* buildTree(vector<int>& arr, int start, int end) {
        if (start > end) return nullptr;
        int center = start + (end - start) / 2;
        TreeNode* node = new TreeNode(arr[center]);
        node->left = buildTree(arr, start, center - 1);
        node->right = buildTree(arr, center + 1, end);
        return node;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return buildTree(nums, 0, nums.size() - 1);
    }
};

반복적 접근

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) return nullptr;
        
        TreeNode* base = new TreeNode(0);
        queue<TreeNode*> nodes;
        queue<int> startIndices;
        queue<int> endIndices;
        
        nodes.push(base);
        startIndices.push(0);
        endIndices.push(nums.size() - 1);

        while (!nodes.empty()) {
            TreeNode* current = nodes.front();
            nodes.pop();
            int low = startIndices.front(); startIndices.pop();
            int high = endIndices.front(); endIndices.pop();
            int mid = low + (high - low) / 2;
            
            current->val = nums[mid];
            
            if (low <= mid - 1) {
                current->left = new TreeNode(0);
                nodes.push(current->left);
                startIndices.push(low);
                endIndices.push(mid - 1);
            }
            
            if (high >= mid + 1) {
                current->right = new TreeNode(0);
                nodes.push(current->right);
                startIndices.push(mid + 1);
                endIndices.push(high);
            }
        }
        return base;
    }
};

538. 이진 탐색 트리를 누적 트리로 변환

재귀적 해결

class Solution {
private:
    int total = 0;
    void traverse(TreeNode* node) {
        if (!node) return;
        traverse(node->right);
        total += node->val;
        node->val = total;
        traverse(node->left);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        total = 0;
        traverse(root);
        return root;
    }
};

반복적 해결

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        int cumulative = 0;
        
        while (cur || !stk.empty()) {
            if (cur) {
                stk.push(cur);
                cur = cur->right;
            } else {
                cur = stk.top();
                stk.pop();
                cumulative += cur->val;
                cur->val = cumulative;
                cur = cur->left;
            }
        }
        return root;
    }
};

669. 이진 탐색 트리 범위 제한

재귀적 방법

class Solution {
public:
    TreeNode* trimBST(TreeNode* node, int minVal, int maxVal) {
        if (!node) return nullptr;
        if (node->val < minVal) 
            return trimBST(node->right, minVal, maxVal);
        if (node->val > maxVal) 
            return trimBST(node->left, minVal, maxVal);
        
        node->left = trimBST(node->left, minVal, maxVal);
        node->right = trimBST(node->right, minVal, maxVal);
        return node;
    }
};

반복적 방법

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int H) {
        if (!root) return nullptr;
        
        while (root && (root->val < L || root->val > H)) {
            if (root->val < L) root = root->right;
            else root = root->left;
        }
        
        TreeNode* ptr = root;
        while (ptr) {
            while (ptr->left && ptr->left->val < L) 
                ptr->left = ptr->left->right;
            ptr = ptr->left;
        }
        
        ptr = root;
        while (ptr) {
            while (ptr->right && ptr->right->val > H) 
                ptr->right = ptr->right->left;
            ptr = ptr->right;
        }
        return root;
    }
};