TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == NULL) return NULL;
        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;
    }

class Solution {
public:
    TreeNode* trimBST1(TreeNode* root, int low, int high) {
        if (root == NULL) return root;
        // 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
        while (root != NULL && (root->val < low || root->val > high)) {
            if (root->val < low) root = root->right;
            else root = root->left;
        }
        TreeNode *cur = root;
        while (cur != NULL) {
            while (cur->left && cur->left->val < low) {
                cur->left = cur->left->right;
            }
            cur = cur->left;
        }
        cur = root;
        while (cur != NULL) {
            while (cur->right && cur->right->val > high) {
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }
        return root;
    }
};

class Solution {
public:
    // 中序遍历递归 左闭右开
    TreeNode* transval(vector<int>& nums, int start, int end) {
        if (end - start == 0) return NULL;
        else if (end - start == 1) {
            TreeNode* cur = new TreeNode(nums[start]);
            return cur;
        }
        else{
            int mid = (start + end) / 2;
            TreeNode* cur = new TreeNode(nums[mid]);
            cur->left = transval(nums, start, mid);
            cur->right = transval(nums, mid + 1, end);
            return cur;
        }
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = NULL;
        root = transval(nums, 0, nums.size());
        return root;
    }
};

class Solution {
public:
    // 代码随想录，迭代法，三个队列 左闭右闭
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() == 0) return nullptr;

        TreeNode* root = new TreeNode(0);   // 初始根节点
        queue<TreeNode*> nodeQue;           // 放遍历的节点
        queue<int> leftQue;                 // 保存左区间下标
        queue<int> rightQue;                // 保存右区间下标
        nodeQue.push(root);                 // 根节点入队列
        leftQue.push(0);                    // 0为左区间下标初始位置
        rightQue.push(nums.size() - 1);     // nums.size() - 1为右区间下标初始位置

        while (!nodeQue.empty()) {
            TreeNode* curNode = nodeQue.front();
            nodeQue.pop();
            int left = leftQue.front(); 
            leftQue.pop();
            int right = rightQue.front(); 
            rightQue.pop();
            int mid = left + ((right - left) / 2);

            curNode->val = nums[mid];       // 将mid对应的元素给中间节点

            if (left <= mid - 1) {          // 处理左区间
                curNode->left = new TreeNode(0);
                nodeQue.push(curNode->left);
                leftQue.push(left);
                rightQue.push(mid - 1);
            }

            if (right >= mid + 1) {         // 处理右区间
                curNode->right = new TreeNode(0);
                nodeQue.push(curNode->right);
                leftQue.push(mid + 1);
                rightQue.push(right);
            }
        }
        return root;
    }
};

class Solution {
public:
	// 递归法
    void transval(TreeNode* cur, int& sum) {
        if (cur->right != NULL) transval(cur->right, sum);
        if (cur != NULL) {
            cur->val += sum;
            sum = cur->val;
        }
        if (cur->left != NULL) transval(cur->left, sum);
    }

    TreeNode* convertBST(TreeNode* root) {
        if (root == NULL) return NULL;
        int sum = 0;
        transval(root, sum); // 注意这里不能直接赋值0,需要用变量名
        return root;
    }
};

class Solution {
public:
    // 右根左 迭代法
    TreeNode* convertBST(TreeNode* root) {
        TreeNode* cur = root;
        stack<TreeNode*> node_stack;
        int sum = 0;
        while (cur || !node_stack.empty()) {
            if (cur != NULL) {
                while (cur) {
                    node_stack.push(cur);
                    cur = cur->right;
                }
            }
            else {
                cur = node_stack.top();
                node_stack.pop();
                cur->val += sum;
                sum = cur->val;
                cur = cur->left;
            }
        }
        return root;
    }
};

class Solution {
public:
    // 统一迭代法
    TreeNode* convertBST(TreeNode* root) {
        if (root == NULL) return NULL;
        stack<TreeNode*> node_stack;
        node_stack.push(root);
        TreeNode* cur = NULL;
        int sum = 0;
        while (!node_stack.empty()) {
            TreeNode* cur = node_stack.top();
            node_stack.pop();
            if (cur != NULL){
                if (cur->left != nullptr) node_stack.push(cur->left);
                node_stack.push(cur);
                node_stack.push(nullptr);
                if (cur->right != nullptr) node_stack.push(cur->right);
            }
            else{
                // 只有遇到空节点的时候，才开始遍历
                cur = node_stack.top();
                cur->val += sum;
                sum = cur->val;
                node_stack.pop();
            }
        }
        return root;
    }
};