代码随想录算法训练营第23天 | 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

发布于 2022-12-06  235 次阅读

AI 摘要

Excerpt: 本文介绍了三道关于二叉搜索树的题目：669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树，分别给出了算法思路和标准答案。对于修剪二叉搜索树，推荐一种递归法和一种迭代法，时间复杂度均为O(logn)，空间复杂度均为O(logn)；对于将有序数组转换为二叉搜索树，思路是以中间节点为分界点，将数组分割成左右两份，然后递归完成即可，时间复杂度为O(n)，空间复杂度为O(n)；对于把二叉搜索树转换为累加树，思路是先找到最右子节点，然后递归地将每个节点的值加上其右子树所有的节点值之和，时间复杂度为O(n)，空间复杂度为O(n)。

669. 修剪二叉搜索树 - 力扣（LeetCode）

思路:

  • 使用递归法，先找到在区间内的节点作为根节点，方法是让此时的根节点与low或者high比较，如果root->val < low，则要去左子树继续找，否则去右子树继续找。若一直未找到符合区间的值，则最终返回nullptr，若找到了，则将该根节点的左子树和右子树分别用同样方法进行修剪，最终返回的root即为修剪完成的二叉树
  • 要注意的是，本题与450. 删除二叉搜索树中的节点 - 力扣（LeetCode）不同，那道题只是删除单独的节点，而本题是一个区间，如果不符合条件可以将整个子树都去掉

我的AC代码

//时间复杂度O(logn),空间复杂度O(logn)
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int low, int high) {
        if(root == nullptr) {
            return nullptr;
        }
        if(root->val < low) {
            return deleteNode(root->right, low, high);
        }
        else if(root->val > high) {
            return deleteNode(root->left, low, high);
        }
        root->left = deleteNode(root->left, low, high);
        root->right = deleteNode(root->right, low, high);
        return root;
    }
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        return deleteNode(root, low, high);
    }
};

标准答案

递归法

//时间复杂度O(logn),空间复杂度O(logn)
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr ) return nullptr;
        if (root->val < low) {
            TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
            return right;
        }
        if (root->val > high) {
            TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点
            return left;
        }
        root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
        root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
        return root;
    }
};

迭代法

//时间复杂度O(logn),空间复杂度O(logn)
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (!root) return nullptr;

        // 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
        while (root != nullptr && (root->val < L || root->val > R)) {
            if (root->val < L) root = root->right; // 小于L往右走
            else root = root->left; // 大于R往左走
        }
        TreeNode *cur = root;
        // 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况
        while (cur != nullptr) {
            while (cur->left && cur->left->val < L) {
                cur->left = cur->left->right;
            }
            cur = cur->left;
        }
        cur = root;

        // 此时root已经在[L, R] 范围内，处理右孩子大于R的情况
        while (cur != nullptr) {
            while (cur->right && cur->right->val > R) {
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }
        return root;
    }
};

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

思路:

  • 思路和已知前中序遍历结果或者已知后中序遍历结果构造唯一二叉树类似，先找到中间节点，即数组的中间，然后以此为分界线将数组分割为左右两份，左边是左子树，右边是右子树，它们的根节点依然是中间部分，左右区间都递归完成即构造完成

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    TreeNode* build(vector<int>& nums, int nbegin, int nend) {
        int nsize = nend - nbegin;
        if(nsize <= 0) {
            return nullptr;
        }
        int sign = (nend + nbegin) / 2;
        TreeNode* root = new TreeNode(nums[sign]);
        if(nsize == 1) {
            return root;
        }
        int lbegin = nbegin;
        int lend = sign;

        int rbegin = sign + 1;
        int rend = nend;

        root->left = build(nums, lbegin, lend);
        root->right = build(nums, rbegin, rend);

        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {

        return build(nums, 0, nums.size());
    }
};

标准答案

递归

//时间复杂度O(n),空间复杂度O(n)
class Solution {
private:
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + ((right - left) / 2);
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid - 1);
        root->right = traversal(nums, mid + 1, right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = traversal(nums, 0, nums.size() - 1);
        return root;
    }
};

迭代法

//时间复杂度O(n),空间复杂度O(n)
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;
    }
};

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

思路:

  • 方法一：遍历两次二叉搜索树，第一次算出二叉搜索树所有节点值的和sum，第二次遍历的时候每遇到一个节点先将sum的值赋给该节点，然后再执行sum -= 节点->val
  • 方法二：反中序遍历二叉搜索树，累加节点值

我的AC代码

遍历两次

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int sum = 0;
    void travel_1(TreeNode* root) {
        if(root == nullptr) {
            return;
        }
        travel_1(root->left);
        sum += root->val;
        travel_1(root->right);
    }
    TreeNode* travel_2(TreeNode* root, int& sum) {
        if(root == nullptr) {
            return nullptr;
        }
        travel_2(root->left, sum);
        int tmp = root->val;
        root->val = sum;
        sum-= tmp;
        travel_2(root->right, sum);
        return root;
    }
    TreeNode* convertBST(TreeNode* root) {
        if(root == nullptr) {
            return nullptr;
        }
        travel_1(root);
        return travel_2(root, sum);
    }
};

标准答案

反中序遍历递归法

//时间复杂度O(n),空间复杂度O(n)
class Solution {
private:
    int pre = 0; // 记录前一个节点的数值
    void traversal(TreeNode* cur) { // 右中左遍历
        if (cur == NULL) return;
        traversal(cur->right);
        cur->val += pre;
        pre = cur->val;
        traversal(cur->left);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};

迭代法

//时间复杂度O(n),空间复杂度O(n)
class Solution {
private:
    int pre; // 记录前一个节点的数值
    void traversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->right;   // 右
            } else {
                cur = st.top();     // 中
                st.pop();
                cur->val += pre;
                pre = cur->val;
                cur = cur->left;    // 左
            }
        }
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};