669. 修剪二叉搜索树
题目描述
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
示例 1：
示例 2：
输入：root = [1,0,2], low = 1, high = 2 输出：[1,null,2]
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3 输出：[3,2,null,1]
示例 3：
输入：root = [1], low = 1, high = 2 输出：[1]
示例 4：
输入：root = [1,null,2], low = 1, high = 3 输出：[1,null,2]
示例 5：
输入：root = [1,null,2], low = 2, high = 4 输出：[2]
思路分析
直接的想法就是递归处理,然后遇到 root->val < low || root->val > high 直接返回NULL.
然而当节点不满足时,还要考虑节点的左右子树是否满足.
如图所示:[1,3]区间对应二叉搜索树还要包括0节点的右子树.即使0节点不满足.
我们发现节点0并不符合区间要求，那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了（就是把节点0从二叉树中移除），然后再递归判断右孩子是否满足.
方法一:递归
递归三部曲:
参数和返回值:参数为要递归的根节点以及low,high俩值. 返回值为满足条件的子树的根节点.
结束条件:当节点为NULL时,结束递归.
单层递归逻辑:如果当前节点在指定范围以左,则向root节点的右子树进行递归; 如果当前节点在指定范围以右,则向root节点的左子树进行递归;如果当前节点在指定范围内则继续向左向右递归,更新其左右子树.
参考代码1
//递归法 TreeNode* trimBST(TreeNode* root, int low, int high) { if(root==nullptr) { //遇到空节点就直接返回NULL return nullptr; } //判断当前节点是否在指定范围内 if(root->val < low) { //如果root在指定范围以左,则向子树的右边进行递归遍历. TreeNode* right = trimBST(root->right,low,high); return right; } if(root->val > high) { //如果root在指定范围以右,则向子树左边进行递归遍历. TreeNode* left = trimBST(root->left,low,high); return left; } //如果当前root值在 指定范围内,则开始进行左递归,右递归 判断其左右子节点是否符合 root->left = trimBST(root->left,low,high); root->right = trimBST(root->right,low,high); return root;//返回构成的新树的根节点 }
方法二:迭代
1.先处理头结点,让其在 指定范围内
2.处理root的左孩子
3.处理root的右孩子
参考代码2
//迭代法 TreeNode* trimBST(TreeNode* root,int low,int high) { if(root==nullptr) { return nullptr; } //处理头结点,让头结点在 指定范围内 while(root!=NULL&&(root->val < low || root->val > high)) { if(root->val < low) { //小于low则向左走 root = root->right; } else { //大于high则向左走 root = root->left; } } TreeNode* cur = root; //处理root的左孩子 while(cur) { while(cur->left &&cur->left->val < low) {//这里的结束条件为节点为NULL cur->left = cur->left->right;//虽然cur->left不满足,但是cur->left->right右边的比cur->left大,也许会有满足的. } cur = cur->left;//如果在 指定范围 内,则继续向左寻找满足条件的节点 } cur = root; //处理root的右孩子(原理相同) while(cur) { while(cur->right && cur->right->val > high ){ cur->right = cur->right->left;//虽然cur->right不满足,但是cur->right->left左边的比cur->right小,也许会有满足的. } cur = cur->right;//如果在 指定范围 内,则继续向右寻找满足条件的节点 } return root; }
108. 将有序数组转换为二叉搜索树
题目描述
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1：
输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例二
输入：nums = [1,3] 输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
思路分析
寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
由于是有序的,所以只要从分割点是中间节点,那么构成的树就是平衡的.
递归三要素:
- 参数和返回值:参数为需要递归的数组以及左右边界,返回值为新构成子树的根节点
- 结束条件:由于是左闭右闭合的,所以如果left > right则返回.
- 单层递归逻辑:确定分割点,以分割点创建根节点,之后构建左子树,构建右子树.
参考代码
//方法一:递归. TreeNode* traversal(vector<int>& nums,int left,int right) { if(left > right) { return NULL; } int mid = left + (right-mid)/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) { return traversal(nums,0,nums.size()-1); }
538. 把二叉搜索树转换为累加树
题目描述
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
示例一:
输入：[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]
思路分析
二叉搜索树中序遍历时,数字是从小到大,由于我们需要的是从大到小进行累加,所以遍历顺序为:右中左. 然后在遍历的时候进行累加即可.
参考代码
//递归法 TreeNode* pre; void traversal(TreeNode* root) { if(root==NULL){ return; } traversal(root->right);//遍历右边 if(pre!=NULL){//中 root->val += pre->val; } pre = root; traversal(root->left);//遍历左边 } TreeNode* convertBST(TreeNode* root){ traversal(root); return root; }
