中山制作网站的公司,皮具网站设计,以营销推广为主题的方案,百度发布信息的免费平台文章目录 669.修建二叉搜索树递归法思路伪代码CPP代码 108.将有序数组转换为二叉搜索树递归伪代码CPP代码 538.把二叉搜索树转换为累加树思路递归伪代码递归CPP代码迭代法 669.修建二叉搜索树 力扣题目链接 文章讲解#xff1a;669.修建二叉搜索树 视频讲解#xff1a;你修剪… 文章目录 669.修建二叉搜索树递归法思路伪代码CPP代码 108.将有序数组转换为二叉搜索树递归伪代码CPP代码 538.把二叉搜索树转换为累加树思路递归伪代码递归CPP代码迭代法 669.修建二叉搜索树 力扣题目链接 文章讲解669.修建二叉搜索树 视频讲解你修剪的方式不对我来给你纠正一下| LeetCode669. 修剪二叉搜索树 状态这个最关键的点在于删除结点之后应该如何接上去 递归法思路
本题中最关键的在于我们应该如何重构BST其实跟我们之前讲的题目删除二叉树中的结点类似。
这题一定要画图模拟才能搞清楚。
伪代码
确定递归函数的参数和返回值本题中有返回值可以大大降低代码难度因为我们可以通过递归函数的返回值移除结点。
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);return right;
}如果root(当前结点)的元素大于high那么应该递归左子树并返回左子树符合条件的头结点 if (root-val high){TreeNode* left trimBST(root-left, 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;CPP代码
#整体代码
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;}
};
#精简代码
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root nullptr) return nullptr;if (root-val low) return trimBST(root-right, low, high);if (root-val high) return trimBST(root-left, low, high);root-left trimBST(root-left, low, high);root-right trimBST(root-right, low, high);return root;}
};108.将有序数组转换为二叉搜索树 力扣题目链接 文章讲解108.将有序数组转换为二叉搜索树 视频讲解构造平衡二叉搜索树| LeetCode108.将有序数组转换为二叉搜索树 状态easy模式其实就是构造二叉树。但是其中的难点在于如何保持平衡呢 递归伪代码
确定递归函数返回值和参数:无论是删除还是增加二叉树的结点都是用递归函数的返回值来完成的这样操作会比较方便。
本题同理依然用递归函数u的返回值来构造中结点的左右孩子。
在构造二叉树的时候尽量不要重新定义左右区间数组而是用下标来操作原数组
//左闭右闭区间[left, right]
TreeNode* traversal(vectorint nums, int left, int right)在这里我们定义好了左闭右闭区间为了遵守循环不变量原则在不断分割的过程中也一定要坚持左闭右闭的原则
确定递归终止条件
这里定义的是左闭右闭的区间所以当区间leftright当时候就是空结点了
if (left right) return nullptr;确定单层递归逻辑
划分区间的时候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;CPP代码
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;}
};538.把二叉搜索树转换为累加树 力扣题目链接 文章讲解538.把 二叉搜索树转换为累加树 视频讲解普大喜奔二叉树章节已全部更完啦| LeetCode538.把二叉搜索树转换为累加树 状态 每个结点都把比他大的结点做一个相加成为新结点值。感觉真的是毫无头绪 思路
直接在二叉树上操作真的很难。但是如果转换思路成一个数组呢
给定一个有序数组我们要将这个数组变成累加数组。
也就是说数组上的每个位置都把其前面位置做一个相加瞬间就能变成一个送分题
就是一个有序数组[2, 5, 13]求从后到前的累加数组也就是[20, 18, 13]是不是感觉这就简单了这里我们对数组的操作要从后向前进行遍历。
那么如果反应到二叉搜索树呢
我们用中序遍历的二叉搜索树是有序数组那么我们进行一个反中序遍历也就是遍历顺序为右中左然后顺序累加即可。那么如何实现这一块代码呢换个顺序即可
递归伪代码
递归函数参数和返回值:在这里我们不需要任何会返回值了最主要的任务就是遍历整颗树
int pre 0;
void traversal (TreeNode* cur)确定终止条件
if (cur NULL) return;单层递归逻辑
右中左遍历二叉树中结点的处理逻辑就是让cur的数值加上前一个结点的数值。
traversal(cur-right);
cur-cur pre;
pre cur-val;
traversal(cur-left;)递归CPP代码
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;}
};迭代法
class Solution {
private:int pre; // 记录前一个节点的数值void traversal(TreeNode* root) {stackTreeNode* st;TreeNode* cur root;while (cur ! NULL || !st.empty()) {if (cur ! NULL) {st.push(cur);cur cur-right; // 右} else {cur st.top(); // 中st.pop();cur-val pre;pre cur-val;cur cur-left; // 左}}}
public:TreeNode* convertBST(TreeNode* root) {pre 0;traversal(root);return root;}
};
