【算法练习Day20】修剪二叉搜索树&&将有序数组转换为二叉搜索树&&把二叉搜索树转换为累加树

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：练题
🎯长路漫漫浩浩，万事皆有期待

修剪二叉搜索树

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

这道题也是有一定的难度的，建议大家先做上一期的删除二叉搜索树的节点。

这道题是给出一个范围，让我们删除该二叉搜索树中的范围以外的全部节点值，并返回调整后的二叉搜索树，也就是说调整了之后，该树仍然是二叉搜索树。该题的难点也是，删除节点时可能会改变二叉搜索树的结构，这一点使得删除节点的题都有一些难度，但是知道了具体套路，就能够应对删除部分的代码了，多做题多总结，才能在删除节点时候考虑的全面。

接下来就是递归逻辑的技巧了，这里我们并不是删除一个节点，而是可能删除一批节点，我们需要用递归逻辑帮助我们删除，我们可以将要删除的节点部分返回空，但是我们并不能直接返回空，因为它的左子树或右子树也有可能是我们需要保留的答案。

具体思路是这样的：我们遍历节点时遇到左边界以外的值，我们进入的是该节点的右子树，因为它的左子树所有值一定都比中间节点小，再去遍历没有必要，我们直接去看它的右子树有没有可以保留的节点，当我们遍历到比右边界大的值，我们要进入它的左子树进行递归，因为它的左子树比我们现在要删的节点小，可能有在范围内的需要保留的节点。

看代码：

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

当然我们在遍历的时候，仍然要用节点来保存，递归后返回，我们的递归逻辑是在下面的，它不止是我们需要删除节点是有用，我们在从头节点一点点往下遍历去寻找的时候，它也起到了向下递归的作用，同时删完节点向上返回时候，它也起到了承接上下链接的作用，而判断语句中的if当前节点是否为空是什么意思呢？

因为我们要遍历整个二叉树来搜索是否有超出边界的值，所以我们在遇到空时候，说明该侧子树没有不符合条件的，也就是需要删除的值，所以我们可以返回null。为什么递归时候没有用到搜索二叉树的性质，这里其实是有使用的，在上面的判断逻辑部分，就能够体现出来，也可以理解是对中间节点的处理，我们将当前数值与边界对比，来判断是进入其左子树还是右子树，这就是运用了搜索树的性质。

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

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

这道题思路不难，但是可惜的是起初仍然做不出来，这道题限制了条件，要得到一个搜索树而且要平衡，搜索树还可以构建，那么平衡树如何构建呢？答案是仍然从数组中做文章，我们直接找到数组的中间部分，每次都以数组的中间位置来做新的中间节点，这样我们将每次都将一个数组从中间分开，就可以得到一个平衡树了，而不需要做其他的判断。

class Solution {
public:
    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;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
       TreeNode* root=traversal(nums,0,nums.size()-1);
       return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

和之前做的那些构造树思路有些许类似，都是需要在数组上找寻构建树的机会。不同的是这道题我们只是找数组中的中间节点，至于如何插入，依靠的是搜索树本身的性质。

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

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

这道题也并不难，但是一开始做的时候，并不理解题目的意思，看了一遍题解才懂。这道题我们需要从后面开始遍历，找到该二叉搜索树的最大节点，在二叉搜索树中，最大节点无疑是右子树里的，次大是中间节点其次才是左子树，我们需要从最大节点开始，通过遍历方式将上一个累加树的值和当前节点值相加，得到新的累加树，将该节点赋予全新的值。实际上就是将第一个数加到第二个要遍历的数上，再将这个数加到第三个数上以此类推，将带有这些节点的树返回，就是一颗累加树，思路并不难。

class Solution {
public:
    int pre=0;
    void traversal(TreeNode* cur)
    {
        if(cur==nullptr)
        {
            return;
        }
        traversal(cur->right);
        cur->val+=pre;
        pre=cur->val;
        traversal(cur->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        pre=0;
        traversal(root);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

总结：

今天我们完成了修剪二叉搜索树、将有序数组转换为二叉搜索树、把二叉搜索树转换为累加树，相关的思想需要多复习回顾。接下来，我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~