二叉树练习day.9

669.修剪二叉搜索树

链接：. - 力扣（LeetCode）

题目描述：

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

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

示例 1：

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

示例 2：

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

提示：

• 树中节点数在范围 [1, 104] 内
• 0 <= Node.val <= 104
• 树中每个节点的值都是 唯一 的
• 题目数据保证输入是一棵有效的二叉搜索树
• 0 <= low <= high <= 104

思路：

与删除二叉树节点的思路一样，遍历二叉树，当前节点如果小于我们需要的区间，则删除该节点的左子树，并且去遍历当前节点的右子树，因为遍历的是二叉树搜索树，因此右子树的值肯定是大于根节点的，不确定右子树的所有元素都在我们需要的区间内，因此需要去遍历，当前节点如果大于我们需要的区间，则删除该节点的右子树，并且去遍历当前节点的左子树，查看是否所有的节点都满足我们的区间

递归实现：

1.确定函数参数和返回值，函数的参数一个为要修剪的二叉树，以及我们的区间范围，返回值应该是修剪后的二叉树

2.确定终止条件，如果当前节点为空，则返回上一个节点，否则查看当前节点的值是否满足我们的条件

3.确定单层递归逻辑，遍历左右子树

代码实现：

/*** 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)return NULL;if(root->val < low){struct TreeNode *tem = root->right;//遍历该节点的右子树，因为右子树比该节点大，但是不一定都在范围内tem = trimBST(root->right, low, high);free(root);return tem;}else if(root->val > high){//遍历该节点的左子树，因为左子树比该节点小，但是不一定都在范围内struct TreeNode *tem = root->left;tem = trimBST(root->left, low, high);free(root);return tem;}root->left = trimBST(root->left,low,high);root->right = trimBST(root->right,low,high);return root;
}

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

链接：. - 力扣（LeetCode）

题目描述：

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵

平衡

二叉搜索树。

示例 1：

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

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 按 严格递增 顺序排列

思路：

与构建二叉树的思路一样，对有序数组进行区间分割，先找到数组中间元素的位置，将其作为根节点，因为数组是递增的，且要构建搜索二叉树，如何按照区间分割的思路来实现

递归实现

1.确定函数的参数和返回值，函数参数应该为有序数组，以及我们要分割的左右区间

2.确定递归终止条件，如果我们数组的左右区间不符合正常情况，则返回空

3.确定单层递归逻辑，找到根节点位置，进行区间的分割，依次创建左右子树

代码实现：

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

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

链接：. - 力扣（LeetCode）

题目描述：

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

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

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

注意：本题和 1038: . - 力扣（LeetCode） 相同

示例 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]

示例 2：

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

示例 3：

输入：root = [1,0,2]
输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

提示：

• 树中的节点数介于 0 和 104 之间。
• 每个节点的值介于 -104 和 104 之间。
• 树中的所有值 互不相同 。
• 给定的树为二叉搜索树。

思路：

根据二叉搜索树的性质，我们可以知道中序遍历（左中右）得到的是一个递增的数组，因为题目要求我们要得到累加树，因此我们就要从右子树开始访问再依次累加，因此我们的递归顺序就变为了右中左，在实现累加操作时，我们需要使用双指针的思路，一个记录当前节点，另一个记录前一个节点的值，用来实现累加

递归实现：

1.确定函数的参数和返回值，因为我们只是要对树每个节点的值进行操作，因此不需要返回值，传入的参数应该是二叉树

2.确定递归的终止条件，当我们二叉树遍历完成时，递归终止

3.确定单层递归逻辑，先去更新右子树，再去处理根节点，最后出来左子树

代码实现：

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