【LeetCode】LeetCode 669.修剪二叉搜索树

LeetCode 669.修剪二叉搜索树

题目链接：https://leetcode.cn/problems/trim-a-binary-search-tree/

题目

解答

递归法

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == NULL)    return NULL;
        if(root->val < low){
            TreeNode* right = trimBST(root->right, low, high);
            return right;
        }

        if(root->val > high){
            TreeNode* left = trimBST(root->left, low, high);
            return left;
        }

        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

迭代法

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == NULL)    return NULL;

        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 != NULL && cur->left->val < low){
                cur->left = cur->left->right;
            }
            cur = cur->left;
        }

        cur = root;

        while(cur != NULL){
            while(cur->right != NULL && cur->right->val > high){
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }
        return root;
    }
};