山东诚祥建设集团公司网站,哪个网站买域名好,中南建设的网站,信息流广告投放公司提示#xff1a;DDU#xff0c;供自己复习使用。欢迎大家前来讨论~ 文章目录 二叉树 Part06二、题目题目一#xff1a;669.修剪二叉搜索树解题思路#xff1a;递归法迭代法#xff1a; 题目二#xff1a; 108.将有序数组转换为二叉搜索树解题思路递归法#xff1a;迭代… 提示DDU供自己复习使用。欢迎大家前来讨论~ 文章目录 二叉树 Part06二、题目题目一669.修剪二叉搜索树解题思路递归法迭代法 题目二 108.将有序数组转换为二叉搜索树解题思路递归法迭代法 题目三538.把二叉搜索树转换为累加树解题思路递归法迭代法 二叉树总结篇二叉树的理论基础二叉树的遍历方式求二叉树的属性二叉树的改造与修改求二叉搜索树的属性二叉树公共祖先问题二叉搜索树的修改与改造 总结 二叉树 Part06
二、题目
题目一669.修剪二叉搜索树
[669. 修剪二叉搜索树](https://leetcode.cn/problems/minimum-absolute-difference-in-bst/)
解题思路
错误的思路
直接想法就是递归处理然后遇到 root-val low || root-val high 的时候直接return NULL一波修改干净利落。
可以写出以下代码
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root nullptr || root-val low || root-val high) return nullptr;root-left trimBST(root-left, low, high);root-right trimBST(root-right, low, high);return root;}
};note
但是会忽略掉删除节点的右子树可能会存在符合的节点但是上面的代码直接删除了所以是不可行的。下图就是示例图 从图中可以看出需要重构二叉树想想是不是本题就有点复杂了。
其实不用重构那么复杂。在上图中我们发现节点0并不符合区间要求那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了就是把节点0从二叉树中移除如图 递归法 确定递归函数的参数以及返回值 这里我们为什么需要返回值呢 因为是要遍历整棵树做修改其实不需要返回值也可以我们也可以完成修剪其实就是从二叉树中移除节点的操作。 但是有返回值更方便可以通过递归函数的返回值来移除节点。 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节点代码如下 这里可能是子树里面还有不符合要求的节点所以还是要遍历一下的。 root-left trimBST(root-left, low, high); // root-left接入符合条件的左孩子
root-right trimBST(root-right, low, high); // root-right接入符合条件的右孩子
return root;Q多余的节点究竟是如何从二叉树中移除的呢 在回顾一下上面的代码针对下图中二叉树的情况 如下代码相当于把节点0的右孩子节点2返回给上一层 if (root-val low) {TreeNode* right trimBST(root-right, low, high); // 寻找符合区间[low, high]的节点return right;
}然后如下代码相当于用节点3的左孩子 把下一层返回的 节点0的右孩子节点2 接住。 root-left trimBST(root-left, low, high);此时节点3的左孩子就变成了节点2将节点0从二叉树中移除了。
完整代码如下
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;}
};迭代法
因为二叉搜索树的有序性不需要使用栈模拟递归的过程。
在剪枝的时候可以分为三步
将root移动到[L, R] 范围内注意是左闭右闭区间剪枝左子树剪枝右子树
class Solution {
public:TreeNode* trimBST(TreeNode* root, int L, int R) {if (!root) return nullptr;// 处理头结点让root移动到[L, R] 范围内注意是左闭右闭while (root ! nullptr (root-val L || root-val R)) {if (root-val L) root root-right; // 小于L往右走else root root-left; // 大于R往左走}TreeNode *cur root;// 此时root已经在[L, R] 范围内处理左孩子元素小于L的情况while (cur ! nullptr) {while (cur-left cur-left-val L) {cur-left cur-left-right;}cur cur-left;}cur root;// 此时root已经在[L, R] 范围内处理右孩子大于R的情况while (cur ! nullptr) {while (cur-right cur-right-val R) {cur-right cur-right-left;}cur cur-right;}return root;}
};小结
题目二 108.将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树
解题思路
本质就是寻找分割点分割点作为当前节点然后递归左区间和右区间。因为有序数组构造二叉搜索树寻找分割点就比较容易了。分割点就是数组中间位置的节点。
Q如果数组长度为偶数中间节点有两个取哪一个
取哪一个都可以只不过构成了不同的平衡二叉搜索树。
例如输入[-10,-3,0,5,9]
如下两棵树都是这个数组的平衡二叉搜索树 如果要分割的数组长度为偶数的时候中间元素为两个是取左边元素 就是树1取右边元素就是树2。
这也是题目中强调答案不是唯一的原因。
递归法 确定递归函数的返回值及参数 这里定义的是左闭右闭区间在不断分割的过程中也会坚持左闭右闭的区间这又涉及之前讲过的循环不变量。 // 左闭右闭区间[left, right]
TreeNode* traversal(vectorint nums, int left, int right)确定递归终止条件 这里定义的是左闭右闭的区间所以当区间 left right的时候就是空节点了。 if (left right) return nullptr;确定单层递归的逻辑
首先取数组中间元素的位置不难写出int mid (left right) / 2;这么写其实有一个问题就是数值越界例如left和right都是最大int这么操作就越界了在二分法中尤其需要注意
**note**所以可以这么写int mid left ((right - left) / 2); int mid left ((right - left) / 2); //首先取数组中间元素的位置
TreeNode* root new TreeNode(nums[mid]); //取了中间位置就开始以中间位置的元素构造节点
root-left traversal(nums, left, mid - 1); //接着划分区间root的左孩子接住下一层左区间的构造节点右孩子接住下一层右区间构造的节点。
root-right traversal(nums, mid 1, right);
return root;这里int mid left ((right - left) / 2);的写法相当于是如果数组长度为偶数中间位置有两个元素取靠左边的。
整体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因为定义的区间为左闭右闭。
迭代法
迭代法可以通过三个队列来模拟一个队列放遍历的节点一个队列放左区间下标一个队列放右区间下标。
模拟的就是不断分割的过程C代码如下
class Solution {
public:TreeNode* sortedArrayToBST(vectorint nums) {if (nums.size() 0) return nullptr;TreeNode* root new TreeNode(0); // 初始根节点queueTreeNode* nodeQue; // 放遍历的节点queueint leftQue; // 保存左区间下标queueint rightQue; // 保存右区间下标nodeQue.push(root); // 根节点入队列leftQue.push(0); // 0为左区间下标初始位置rightQue.push(nums.size() - 1); // nums.size() - 1为右区间下标初始位置while (!nodeQue.empty()) {TreeNode* curNode nodeQue.front();nodeQue.pop();int left leftQue.front(); leftQue.pop();int right rightQue.front(); rightQue.pop();int mid left ((right - left) / 2);curNode-val nums[mid]; // 将mid对应的元素给中间节点if (left mid - 1) { // 处理左区间curNode-left new TreeNode(0);nodeQue.push(curNode-left);leftQue.push(left);rightQue.push(mid - 1);}if (right mid 1) { // 处理右区间curNode-right new TreeNode(0);nodeQue.push(curNode-right);leftQue.push(mid 1);rightQue.push(right);}}return root;}
};小结
递归思路提到了递归方法的核心思路是不断进行中间分割然后递归地处理左区间和右区间这也是一种分治策略。递归函数的返回值通过递归函数的返回值来增删二叉树是常规操作。循环不变量的重要性在定义区间的过程中再次强调了循环不变量的重要性这可能是在递归或迭代过程中保持逻辑一致性的关键。迭代方法这实际上是模拟取中间元素然后不断分割去构造二叉树的过程。递归与迭代的比较虽然递归方法可能更直观但迭代方法提供了另一种解决问题的途径特别是在某些情况下可能更高效或更适合某些应用场景。
题目三538.把二叉搜索树转换为累加树
538. 把二叉搜索树转换为累加树
解题思路
当我们面对累加二叉搜索树的问题时可能会感到困惑因为直观上它看起来比操作数组要复杂。使得每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。但一旦我们认识到二叉搜索树的有序性问题就变得简单了。就像处理一个有序数组[2, 5, 13]我们可以从后向前进行累加得到新的数组[20, 18, 13]。这种遍历方式在数组中很常见而在二叉搜索树中我们只需要调整遍历的顺序采用反中序遍历即先遍历右子树然后是根节点最后是左子树就可以实现同样的顺序累加。这样一来原本看似复杂的累加操作就变成了一个简单的遍历和累加过程。
递归法
pre指针的使用技巧: 本题依然需要一个pre指针记录当前遍历节点cur的前一个节点这样才方便做累加。
递归三部曲 确定递归函数的返回值和参数 nt pre 0; // 记录前一个节点的数值
void traversal(TreeNode* cur)确定递归函数的终止条件 if (cur NULL) return;确定单层循环逻辑 注意要右中左来遍历二叉树 中节点的处理逻辑就是让cur的数值加上前一个节点的数值。 traversal(cur-right); // 右
cur-val pre; // 中
pre cur-val;
traversal(cur-left); // 左完整代码如下
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;}
};二叉树总结篇
二叉树的理论基础
二叉树的种类、存储方式、遍历方式、定义方式
二叉树的遍历方式
深度优先遍历广度优先遍历
求二叉树的属性
二叉树的改造与修改
求二叉搜索树的属性
二叉树公共祖先问题
二叉搜索树的修改与改造
小结
note二叉树的遍历顺序的选择
如果是要构造二叉树无论是普通的二叉树还是二叉搜索树通常都是先处理根节点也就是前序遍历。当我们想要计算普通二叉树的一些属性时后序遍历是个不错的选择因为这样可以在访问节点之前先得到其左右子树的信息通常需要通过递归函数的返回值来进行计算。而对于二叉搜索树由于其元素是有序的中序遍历是最佳选择因为这样可以直接利用树的有序性比如进行排序或查找操作。
注意在普通二叉树的属性中用的是一般为后序例如单纯求深度就用前序二叉树找所有路径 (opens new window)也用了前序这是为了方便让父节点指向子节点。
所以求普通二叉树的属性还是要具体问题具体分析才能让问题变得简洁。 总结
学到了那些东西:
二叉树的构造前序构造二叉树的遍历方式前中后递归和迭代一般递归的思路来的比较简单代码也是比较简洁。递归三部曲1.2.3。pre指针的使用这是一个技巧。看到二叉搜索树一定要记得利用他的特性有序。在本节迭代的代码也是比较简单的。
关于二叉树的章节今天是完结篇整体下来学的有些稀里糊涂大概过了一边顺了一遍思路。很多题目自己为了节省时间还有偷懒就没有自己亲手去敲的不知道是因为自己太懒还是太烂总有畏难情绪觉得自己敲了也敲不对敲了也没用只是浪费时间就有些投机取巧没有去敲。这样下来总感觉收获很少但哪位老板能和我说一下你们是怎么坚持每题都敲代码的吗这对我很重要
总之二叉树这一个章节也是结束了马上要开始一个新的章节回溯杜绝懒惰从我做起加油
