二叉树练习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] <= 104nums按 严格递增 顺序排列
思路：
与构建二叉树的思路一样，对有序数组进行区间分割，先找到数组中间元素的位置，将其作为根节点，因为数组是递增的，且要构建搜索二叉树，如何按照区间分割的思路来实现
递归实现
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; }