摘要

• 修剪二叉搜索树，通过递归函数的返回值来对节点的left和right进行赋值来实现删除节点的操作。

• 构造二叉搜索树与之前用数组构造二叉树的思想类似，只是划分数组的规则不同。构造二叉搜索树的划分规则为取升序数组的中间值作为根节点。

• 将二叉树转为累加树用到了异构的中序遍历，即反中序遍历（“右中左”），这样得到的序列是降序序列。

LeetCode669 修剪二叉搜索树

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

• 二叉搜索树的性质可以帮助我们确定修剪的方向，设当前访问的节点为cur
  • 如果cur->val < low，说明当前节点及其左子树都小于low，都应该被修剪；此时应该将cur->right接到cur的位置上。
  • 但cur的右子树也可能需要修剪，所以不能简单的将右子树接回去，而是要对右子树修剪后再接回去，这就需要递归调用
  • 如果cur->val > high同理
• 采用递归法实现：
  • 传入的参数和返回值：传入当前子树的根节点，修剪的下界low和上界high；返回修剪后的子树的根节点。
  • 递归的终止条件：访问到空节点，无需修剪，直接返回；访问到值不在修剪区间内的节点，若cur->val < low则返回其修剪后的右子树，cur->val > high则返回其修剪后的左子树。
  • 单层递归的处理逻辑：如果当前节点需要修剪，则在终止条件中处理，如果当前节点不需要修剪，则修剪其左子树和右子树。

完整题解代码如下

class Solution {
public:
    void delTree(TreeNode* root) {
        if (!root) return;
        delTree(root->left);
        delTree(root->right);
        delete root;
    }
    TreeNode* trim(TreeNode* root, int& low, int& high) {
        if (!root) return nullptr;
        if (root->val < low) {
            TreeNode* right = trim(root->right, low, high);
            // delTree(root->left);
            // delete root;
            return right;
        }
        if (root->val > high) {
            TreeNode* left = trim(root->left, low, high);
            // delTree(root->right);
            // delete root;
            return left;
        }
        root->left = trim(root->left, low, high);
        root->right = trim(root->right, low, high);
        return root;
    }
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        return trim(root, low, high);
    }
};

如何删除要被修剪的节点呢？

• 叶节点：叶节点调用一次trim会访问到空节点，然后将空节点返回给上一层节点的left或right
• 非叶节点：调用一次trim会将其左子树或右子树返回给上一层节点的left或right。

附LeetCode环境下的内存释放问题，不知道是不是因为递归过程中重复delete导致报错。

来自群内大佬讨论

LeetCode108 将有序数组转换为二叉搜索树

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

• 也和用中序和后序构造二叉树类似，有序数组转换为二叉搜索树的划分规则就是找数组的中间的值，然后用中位数作为根节点的值，将数组划分为左子树对应的数组和右子树对应的数组。

• 可以理解为前序遍历，因为需要先构造当前节点，再去向下构造左子树和右子树。

• 采用左闭右开区间来划分数组，采用递归法实现

  • 传入的参数和返回值：当前子树对应的数组及对应的下标区间；返回当前子树的根节点
  • 递归终止条件：区间内没有值，返回nullptr；区间内有一个值，说明到达叶节点，构造叶节点后直接返回。
  • 单层递归的处理逻辑：找到数组的中位的值，作为当前子树的根节点，然后构造左子树和右子树。

递归法

class Solution {
public:
    TreeNode* constructBST(vector<int>& nums, int l, int r) {
        if (l >= r) return nullptr;
        // if (r - l == 1) return new TreeNode(nums[l]);
        int delim = (l + r) / 2;
        TreeNode* root = new TreeNode(nums[delim]);
        root->left = constructBST(nums, l, delim);
        root->right = constructBST(nums, delim + 1, r);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return constructBST(nums, 0, nums.size());
    }
};

需要注意的是，像下面这样求数组中间的值的下标可能会造成int溢出

int delim = (l + r) / 2;

可以改为

int delim = l + (r - l) / 2;

LeetCode538 把二叉搜索树转换为累加树

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

• 对二叉搜索树进行中序遍历，可以的得到一个升序序列

image.png

• 如上图，中序遍历后得到

二叉搜索树: {0, 1, 2, 3, 4, 5, 6, 7, 8}

• 按累加树的定义，对以上序列从右向左，能很方便的进行累加

二叉搜索树: {0, 1, 2, 3, 4, 5, 6, 7, 8}
累加树   : {36, 36, 35, 33, 30, 26, 21, 15, 8}

• 可见，只要按“右中左”的顺序对二叉树进行遍历，就能很方便的将二叉搜索树转换为累加树

完整题解代码如下

class Solution {
public:
    TreeNode* convertBSTtoGST(TreeNode* cur, TreeNode*& pre) {
        if (!cur) return nullptr;
        TreeNode* right = convertBSTtoGST(cur->right, pre);
        if (pre) cur->val += pre->val;
        pre = cur;
        TreeNode* left = convertBSTtoGST(cur->left, pre);
        return cur;
    }
    TreeNode* convertBST(TreeNode* root) {
        TreeNode* pre = nullptr;
        return convertBSTtoGST(root, pre);
    }
};