好看的知名企业网站,好看欧美视频网站模板下载 迅雷下载 迅雷下载地址,网站开发策略都有啥,中国招标建设信息网站目录
LeetCode: 669. 修剪二叉搜索树
基本思路
C代码
LeetCode: 108.将有序数组转换为二叉搜索树
基本思路
C代码
LeetCode: 538.把二叉搜索树转换为累加树
基本思路
C代码 LeetCode: 669. 修剪二叉搜索树 力扣代码链接 文字讲解#xff1a;LeetCode: 669. 修剪二叉搜…目录
LeetCode: 669. 修剪二叉搜索树
基本思路
C代码
LeetCode: 108.将有序数组转换为二叉搜索树
基本思路
C代码
LeetCode: 538.把二叉搜索树转换为累加树
基本思路
C代码 LeetCode: 669. 修剪二叉搜索树 力扣代码链接 文字讲解LeetCode: 669. 修剪二叉搜索树 视频讲解你修剪的方式不对我来给你纠正一下 基本思路 这个题目比较简单但是一定要注意遇到节点在目标区间以外不能直接返回null而是应该继续向下判定因为对于一个搜索二叉树来讲在遍历整个二叉树的节点的过程中如果某个节点的值小于区间的最小值对于该节点的左子树中的所有节点一定都小于目标区间的最小值但是右子树中却可能存在符合目标区间的值因此还需要进一步进行判定。
确定递归函数的参数以及返回值 参数需要传入当前遍历的节点还需要传入目标取件的边界值low和high。 返回值返回需要删除的节点。
TreeNode* trimBST(TreeNode* root, int low, int high)
确定终止条件 修剪的操作并不是在终止条件上进行的所以就是遇到空节点返回就可以了。
if (root nullptr ) return nullptr;
确定单层递归的逻辑 如果root当前节点的元素小于low的数值那么应该递归右子树并返回右子树符合条件的头结点。
if (root-val low) {TreeNode* right trimBST(root-right, low, high); // 寻找符合区间[low, high]的节点return right;
} 如果root(当前节点)的元素大于high的那么应该递归左子树并返回左子树符合条件的头结点。
if (root-val high) {TreeNode* left trimBST(root-left, low, high); // 寻找符合区间[low, high]的节点return left;
} 接下来要将下一层处理完左子树的结果赋给root-left处理完右子树的结果赋给root-right。
root-left trimBST(root-left, low, high); // root-left接入符合条件的左孩子
root-right trimBST(root-right, low, high); // root-right接入符合条件的右孩子
return root;
C代码
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;}
};
LeetCode: 108.将有序数组转换为二叉搜索树 力扣代码链接 文字讲解LeetCode: 108.将有序数组转换为二叉搜索树 视频讲解构造平衡二叉搜索树 基本思路 构建平衡二叉树是为因为给定任意一个有序数组都可以直接构建一颗线性结构的二叉树。而构建二叉树我们首先就应该想到根据数组构建二叉树本质就是寻找分割点分割点作为当前节点然后递归左区间和右区间。分割点就是数组中间位置的节点。
确定递归函数返回值及其参数 参数需要传入一个有序数组并且需要传入数组的左右下标根据数组的左右下标来构建二叉树 返回值返回构建二叉树的根节点。
// 左闭右闭区间[left, right]
TreeNode* traversal(vectorint nums, int left, int right) 这里注意我这里定义的是左闭右闭区间在不断分割的过程中也会坚持左闭右闭的区间这又涉及到我们讲过的循环不变量原则。
确定递归终止条件 这里定义的是左闭右闭的区间所以当区间leftright当时候就是空结点了。
if (left right) return nullptr;
确定单层递归的逻辑 根据数组区间的左右下标来构建二叉树其中二叉树的根节点为mid left(right-left)/2,此时中间节点为
TreeNode* root new TreeNode(nums[mid]); 接着划分区间root的左孩子接住下一层左区间的构造节点右孩子接住下一层右区间构造的节点最后返回root节点。
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;
C代码
class Solution {
private:TreeNode* traversal(vectorint 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;}
public:TreeNode* sortedArrayToBST(vectorint nums) {TreeNode* root traversal(nums, 0, nums.size() - 1);return root;}
}; 注意在调用traversal的时候传入的left和right为什么是0和nums.size() - 1因为定义的区间为左闭右闭。
LeetCode: 538.把二叉搜索树转换为累加树 力扣代码链接 文字讲解LeetCode: 538.把二叉搜索树转换为累加树 视频讲解普大喜奔二叉树章节已全部更完啦 基本思路 其实这就是一棵树大家可能看起来有点别扭换一个角度来看这就是一个有序数组[2, 5, 13]求从后到前的累加数组也就是[20, 18, 13]是不是感觉这就简单了。 为什么变成数组就是感觉简单了呢 因为数组大家都知道怎么遍历啊从后向前挨个累加就完事了这换成了二叉搜索树看起来就别扭了一些是不是。那么知道如何遍历这个二叉树也就迎刃而解了从树中可以看出累加的顺序是右中左所以我们需要反中序遍历这个二叉树然后顺序累加就可以了。
递归函数参数以及返回值 首先需要定义一个全局变量pre用来记录前一个节点的值。 参数传入当前节点 返回值只需要对遍历的节点的值进行操作不需要什么返回值。
int pre 0; // 记录前一个节点的数值
void traversal(TreeNode* cur)
确定终止条件 遇空节点就终止。
if (cur NULL) return;
确定单层递归的逻辑 注意要右中左来遍历二叉树 中节点的处理逻辑就是让cur的数值加上前一个节点的数值。
traversal(cur-right); // 右
cur-val pre; // 中
pre cur-val;
traversal(cur-left); // 左
C代码
class Solution {
private:int pre 0; // 记录前一个节点的数值void traversal(TreeNode* cur) { // 右中左遍历if (cur NULL) return;traversal(cur-right);cur-val pre;pre cur-val;traversal(cur-left);}
public:TreeNode* convertBST(TreeNode* root) {pre 0;traversal(root);return root;}
};
