Day20.一刷数据结构算法(C语言版) 669修剪二叉搜索树；108将有序数组转换为二叉搜索树；538把二叉搜索树转换为累加树

一、669修剪二叉搜索树

        这道题目比较难，比添加增加和删除节点难的多，建议先看视频理解。

        题目链接：修剪二叉搜索树

        文章讲解：代码随想录

        视频讲解：你修剪的方式不对，我来给你纠正一下！| 修剪二叉搜索树

1.思路分析

直接想法就是：递归处理，然后遇到 root == NULL || root->val < low || root->val > high 的时候直接return NULL，一波修改，赶紧利落。

然而[1, 3]区间在二叉搜索树的中可不是单纯的节点3和左孩子节点0就决定的，还要考虑节点0的右子树。

我们在重新关注一下第二个示例，如图：

所以上面的想法是不可行的！

但其实也不用像重构那么复杂。

在上图中我们发现节点0并不符合区间要求，那么将节点0的右孩子节点2 直接赋给节点3的左孩子就可以了（就是把节点0从二叉树中移除），如图：

递归三部曲：

1）确定递归函数的参数以及返回值

因为是要遍历整棵树做修改，其实不需要返回值也可以，我们也可以完成修剪（其实就是从二叉树中移除节点）的操作。

但是有返回值更方便，可以通过递归函数的返回值来移除节点。

这样的做法在搜索树中的插入操作和搜索树中的删除操作中大家已经了解过了。

struct TreeNode* trimBST(struct TreeNode* root, int low, int high)

2）确定终止条件

 if (root == NULL) return NULL;

3）确定单层递归逻辑

如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。

if (root->val < low) {
    struct TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
    return right;
}
//而对于多余的节点，上面的代码相当于把节点0的右孩子（节点2）返回给上一层。

如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。

if (root->val > high) {
    struct TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点
    return left;
}

接下来要将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right。

最后返回root节点。代码如下：

root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
//上面的代码相当于用节点3的左孩子把下一层返回的节点0的右孩子（节点2） 接住。

root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
return root;

而此时节点3的左孩子就变成了节点2，将节点0从二叉树中移除了。

2.代码详解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* trimBST(struct TreeNode* root, int low, int high) {
        if (root == NULL) return NULL;
        if (root->val < low) {
            struct TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
            return right;
        }
        if (root->val > high) {
            struct 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;
    }

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

        这道题就简单一些，可以尝试先自己做做。

        题目链接：将有序数组转换为二叉搜索树

        文章链接：代码随想录

        视频讲解：构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树

1.思路分析

题目中说要转换为一棵高度平衡二叉搜索树。为什么强调要平衡呢？

因为只要给我们一个有序数组，如果不强调平衡，都可以以线性结构来构造二叉搜索树。

例如有序数组[-10，-3，0，5，9] 就可以构造成这样的二叉搜索树，如图：

上图中，是符合二叉搜索树的特性吧，但如果要这么做的话，是不是本题意义就不大了，所以才强调是平衡二叉搜索树。

其实数组构造二叉树，构成平衡树是自然而然的事情，因为大家默认都是从数组中间位置取值作为节点元素，一般不会随机取。

至于如何将数组构建成二叉树，本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。

二叉搜索树的分割点就是数组中间位置的节点。

那么为问题来了，如果数组长度为偶数，中间节点有两个，取哪一个？

取哪一个都可以，只不过构成了不同的平衡二叉搜索树。

如果要分割的数组长度为偶数的时候，中间元素为两个，是取左边元素就是树1，取右边元素就是树2。

这也是题目中强调答案不是唯一的原因。理解这一点，这道题目算是理解到位了。

递归三部曲：

1）确定递归函数返回值及其参数

本题要构造二叉树，依然用递归函数的返回值来构造中节点的左右孩子。

再来看参数，首先是传入数组，然后就是左下标left和右下标right，我们在构造二叉树的时候尽量不要重新定义左右区间数组，而是用下标来操作原数组。

struct TreeNode* traversal(int* nums, int left, int right)

这里注意，我这里定义的是左闭右闭区间，在不断分割的过程中，也会坚持左闭右闭的区间，这又涉及到我们讲过的循环不变量。

2）确定递归终止条件

这里定义的是左闭右闭的区间，所以当区间 left > right的时候，就是空节点了。

if (left > right) return NULL;

3）确定单层递归逻辑

首先取数组中间元素的位置，不难写出int mid =(right +left) / 2;

这么写其实有一个问题，就是数值越界，例如left和right都是最大int，这么操作就越界了，在二分法中尤其需要注意！

所以可以这么写：int mid = left + ((right - left) / 2);

但本题leetcode的测试数据并不会越界，所以怎么写都可以。但需要有这个意识！

取了中间位置，就开始以中间位置的元素构造节点：struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));

接着划分区间，root的左孩子接住下一层左区间的构造节点，右孩子接住下一层右区间构造的节点。

最后返回root节点，单层递归整体代码如下：

int mid = left + ((right - left) / 2);
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = nums[mid];
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;

这里int mid = left + ((right - left) / 2);的写法相当于是如果数组长度为偶数，中间位置有两个元素，取靠左边的。

2.代码详解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* traversal(int* nums, int left, int right) {
    if (left > right) 
        return NULL;
    int mid = left + ((right - left) / 2);
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = nums[mid];
    root->left = traversal(nums, left, mid - 1);
    root->right = traversal(nums, mid + 1, right);
    return root;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    struct TreeNode* root = traversal(nums, 0, numsSize - 1);
    return root;
}

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

        本题也不难，在求二叉搜索树的最小绝对差和众数那两道题目都讲过了双指针法，思路是一样的。

        题目链接：把二叉树搜索树转换为累加树

        文章链接：代码随想录

        视频讲解：普大喜奔！二叉树章节已全部更完啦！| 把二叉搜索树转换为累加树

1.思路分析

有序的元素如何求累加呢？

其实这就是一棵树，大家可能看起来有点别扭，换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，是不是感觉这就简单了。

为什么变成数组就是感觉简单了呢？

因为数组大家都知道怎么遍历啊，从后向前，挨个累加就完事了，这换成了二叉搜索树，看起来就别扭了一些是不是。

那么知道如何遍历这个二叉树，也就迎刃而解了，从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。

递归顺序如图所示：

本题依然需要一个pre指针记录当前遍历节点cur的前一个节点，这样才方便做累加。

pre指针的使用技巧，我们在二叉树：搜索树的最小绝对差和二叉树：我的众数是多少？都提到了，这是常用的操作手段。

递归三部曲：

1）递归函数参数以及返回值

这里很明确了，不需要递归函数的返回值做什么操作了，要遍历整棵树。

同时需要定义一个全局变量pre，用来保存cur节点的前一个节点的数值，定义为int型就可以了。

int pre;
void traversal(struct TreeNode* node)

2）确定终止条件

if(!node) return ;

3）确定单层递归逻辑

注意要右中左来遍历二叉树，中节点的处理逻辑就是让cur的数值加上前一个节点的数值。

traversal(node->right);
node->val = node->val + pre;
pre = node->val;
traversal(node->left);

2.代码详解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int pre;
void traversal(struct TreeNode* node) {
    if(!node)
        return ;
    traversal(node->right);
    node->val = node->val + pre;
    pre = node->val;
    traversal(node->left);
}

struct TreeNode* convertBST(struct TreeNode* root){
    pre = 0;
    traversal(root);
    return root;
}

二叉树部分结束。

如果你有问题或者有其他想法，欢迎评论区留言，大家可以一起探讨。