526互联

算法学习Day23二叉搜索树的修剪，转化

发布时间 2024-01-04 20:17:50作者: HQWQF

Day23二叉搜索树的修剪，转化

By HQWQF 2024/01/04

笔记

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：

输入： root = [1,0,2], low = 1, high = 2输出：[1,null,2]

递归法

修剪相当于删除超过一定范围的节点，但是我们可以利用二叉搜索树的结构减少计算量，比如找到了一个小于范围的节点时，我们往这个节点的右子树进行查找（右子树的值大于该节点值但小于节点的父节点），找到第一个值在范围内的节点就将节点的父节点的左支指向这个节点。

为什么是父节点的左支，因为该节点小于范围而父节点在范围中，所以父节点值大于该节点。

大于范围的情况也同理。

我们遍历树中的每个节点（其实并没有），如果不在范围就执行上述过程。

递归法代码

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr) return nullptr;
        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* 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.将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入： nums = [-10,-3,0,5,9]输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

递归法

题目要求是平衡的，因为如果不要求平衡，直接数组转化成链表就行了。

我们知道，二叉搜索树的中序遍历是有序的，那么我们也可以将有序数组看作二叉搜索树的中序遍历结果，将有序数组中间的节点作为根节点就能确保平衡，确定根节点后我们将其分割出的两个数组按照一样的办法递归转化为二叉搜索树，并赋值给根节点的两支。

递归法代码

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return traversal(nums,0,nums.size()-1);
    }
    TreeNode* traversal(vector<int>& nums, int left, int right)
    {
        if(left>right){return nullptr;}
        //当使用 （left + right) >> 1;时，如left和right都是int最大值，结果就会溢出
        int midindex = left + ((right - left) >> 1);
        TreeNode* root = new TreeNode(nums[midindex]);
        root->left = traversal(nums,left,midindex-1);
        root->right = traversal(nums,midindex+1,right);
        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;
    }
};

538.把二叉搜索树转换为累加树

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

递归法

我们知道二叉搜索树的中序遍历是升序的，我们可以中序遍历二叉搜索树，然后用其后的元素（即大于的）累加去处理遍历到的节点，但是这样在遍历时就必须提前知道后面的值。

我们可以反中序遍历二叉搜索树，得到降序的顺序，这样我们就可以在遍历中累加已经遍历到的值，处理遍历到的节点只需要将这个值加到节点值上就行。

递归法代码

class Solution {
public:
    int count = 0;
    TreeNode* convertBST(TreeNode* root) {
        count = 0;
        test(root);
        return root;

    }
    void traversal(TreeNode* root)
    {
        if(root == nullptr){return;}
        traversal(root->right);
        int tmp = root->val;
        root->val += count;
        count += tmp;
        traversal(root->left);
    }
};

上面我们有一个变量去存储当前已经累加的值，但是这样就必须在处理当前节点值时使用一个临时变量，我们可以使用一个pre变量存储上一个节点处理后的值，这个值和count 是一样的，但是就不需要使用临时变量了。

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;
    }
};

迭代法

迭代法也是一样的思路

迭代法代码

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;
    }
};