上饶百度网站建设,长春高铁建站,投资网站怎么做,wordpress不发送邮件654.最大二叉树#xff1a; 文档讲解#xff1a;代码随想录|654.最大二叉树 视频讲解#xff1a;又是构造二叉树#xff0c;又有很多坑#xff01;| LeetCode#xff1a;654.最大二叉树_哔哩哔哩_bilibili 状态#xff1a;已做出 思路#xff1a;
这道题目要求使用给定…654.最大二叉树 文档讲解代码随想录|654.最大二叉树 视频讲解又是构造二叉树又有很多坑| LeetCode654.最大二叉树_哔哩哔哩_bilibili 状态已做出 思路
这道题目要求使用给定的数组创建一个最大二叉树递归是使用分治思想来解决找到数组最大值把这个最大值前后区域分开分别再对子数组进行判断这样不断的划分子数组递归函数返回值是树节点递归函数里每次都使用循环找到最大节点后这个节点的左右子树通过递归来创建递归后就成功创建了要求的二叉树。递推算是这道题目的最优解吧递推是用来了单调栈使用单调栈遍历数组单调栈里面维护单调递增每次遍历到一个数组的元素后把小于此时遍历到的数组元素的栈顶元素都删除这样栈里的元素就是能保证递增随后在每层判断时如果数组元素大于栈顶元素那么就让栈顶元素设置成数组元素节点的左子树这个操作是个循环每次大于栈顶元素就改变一次数组元素结点的左子树这样就能让此时遍历的数组元素左子树指向子区域最大值如果站顶元素大于数组元素就让栈顶义元素的右子树指向数组元素节点这样不断递归就能建立最大二叉树了。
递归(时间复杂度是n^2)
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public://使用索引进行分治TreeNode* dfs(vectorint num,int l,int r) {if(lr) return nullptr; //当索引出现异常结束递归int Maxnum[l]; //先对这个最大值进行初始化用来保存最大值int xidl; //这个用来保存最大值的下标//通过循环找到这个区域的最大值for(int il1;ir;i) {if(num[i]Max) {Maxnum[i];xidi;}}TreeNode* rootnew TreeNode(Max); //创建新节点//创建根的左右子树root-leftdfs(num,l,xid-1);root-rightdfs(num,xid1,r);return root;}TreeNode* constructMaximumBinaryTree(vectorint nums) {TreeNode* rootdfs(nums,0,nums.size()-1);return root;}
};
递推(使用两个栈操作过程过于繁琐时间复杂度4n)
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* constructMaximumBinaryTree(vectorint nums) {stackTreeNode*st;//创建栈这个栈用来维护递增单调栈if(nums.size()0) return nullptr;stackTreeNode*tempst; //这个栈用来保存从st栈出的元素st.push(new TreeNode(nums[0])); //初始化栈int dix1;TreeNode* root; //最终创建树的根while(!st.empty()) {//这里的循环一共分为了两个部分一个部分是数组未遍历完一个是数组已遍历完毕if(nums.size()dix) {TreeNode* tempnew TreeNode(nums[dix]);//创建临时节点//这里循环让小于此时遍历的数组元素的栈元素都出栈并让出栈的元素插入到tempst里这里就是维护单调栈的操作while(!st.empty() temp-valst.top()-val) {tempst.push(st.top());st.pop();}//下面就是处理tempst栈的操作st.push(temp);if(!tempst.empty()) {//tempst栈里的元素都小于此下标的数组并且栈是从栈顶到栈底递减所以都处理成上一个左子树st.top()-lefttempst.top();TreeNode* ttempst.top();tempst.pop();//下面就是对tempst所有的节点元素进行左子树的连接while(!tempst.empty()) {t-righttempst.top();ttempst.top();tempst.pop();}}}else {//st剩下的节点元素必定是递增的所以都以右子树操作连接TreeNode* curst.top();st.pop();if(!st.empty())st.top()-rightcur;else rootcur;}}return root;}
};
递推(通过ai优化只用了一个栈时间复杂度优化到了2n)
class Solution {
public:TreeNode* constructMaximumBinaryTree(vectorint nums) {stackTreeNode* stk;for (int i 0; i nums.size(); i) {TreeNode* curr new TreeNode(nums[i]);// 小于当前值的节点是当前节点的左孩子while (!stk.empty() stk.top()-val nums[i]) {curr-left stk.top();stk.pop();}// 当前节点是栈顶元素的右孩子if (!stk.empty()) {stk.top()-right curr;}stk.push(curr);}// 栈底就是根节点while (stk.size() 1) stk.pop();return stk.top();}
};
遇到的困难
这道题目最开始应该做过类似的所以递归的分治做法不是很难当时主要在思考怎么去用单调栈优化时间复杂度因为递归每层都会使用到循环来找最大值时间复杂度绝对不是最优解所以去查看了最优解的方法是使用单调栈。最初单调栈最难想到的就是怎么去正确处理出栈和入栈的左右子树的指向感觉这个很难处理当时出现了很多大大小小的问题还有循环和if语句的条件处理都没处理好导致错了很多次我最初的思路是把整体遍历分为两个部分一个是数组未遍历完的操作一个是数组遍历完的操作为了处理好出栈入栈的操作我设置了两个栈来辅助操作一个栈用来保存出栈的较小节点一个几也是单调栈这个较小栈保存出栈的所有节点最后这个较小栈的栈顶元素必定是这个栈里最大的结点然后就是让这个较小栈里的节点元素的右子树都指向下一个栈顶的结点这样就能完成处理右子树建立的问题最后数组遍历完后单调栈剩下的就是递增节点了全部都右子树处理既可。但这种方式太过复杂处理起来太麻烦而且这种方式其实时间复杂度是4n因为每个结点要出入栈两次最后ai优化后才把时间复杂度优化为2n只使用了一个栈。
收获
这道题目的优化解法让我接触到了单调栈这个用法之前接触过单调队列的题目这次终于遇到了单调栈的题型了也是体验到了单调栈的妙处通过单调栈的出栈入栈让强行让数组的所有节点都出栈入栈一次就可以成功创建最大树。不过分治思想递归也是一种很好的方法使用分治思想更能体现出二叉树的特点。 617.合并二叉树 文档讲解代码随想录|617.合并二叉树 视频讲解一起操作两个二叉树有点懵| LeetCode617.合并二叉树_哔哩哔哩_bilibili 状态已做出 思路
这道题目要求我们合并二叉树我也是使用了递归和递推两种方法首先递归就是同时对两个二叉树的节点进行递归这个递归函数的返回值就是节点指针递归函数内部首先判断此时递归的两个二叉树节点是否都为空是就直接结束递归随后使用三段else-if语句来对此层合并节点的处理如果递归的这两个二叉树节点都为非空合并的val值就是两个val值的和然后使用两个递归分别递归这两个二叉树的左右子树来建立合并后树的左右子树如果一处为空那和并的val值就是非空的那一个节点的val值随后对这两个儿茶素递归时一个二叉树为空的那个位置传入的参数就是空最后if语句判断完后返回合并后树的节点既可完成合并操作。递推当时我对合并二叉树有一个致命的误解导致编写代码出现了很大的问题我没有意识到合并合并二叉树出现一个二叉树节点为空一个不为空时可以直接加入这个非空的这个节点以及后序所有子结点都没有必要再进行判断了这点当时并没有发现我第一次实现递推代码非常繁琐编写代码直接是把空的情况也考虑进去了然而为空的情况本来就可以直接加上这一整个子树就可以了后续为空的情况完全不需要去额外考虑文档给出了最简洁的代码我最后靠ai优化的代码也还是考虑到了空节点导致不必要的时间消耗就是使用tupleTreeNode*TreeNode*TreeNode*为元素的栈这三个元素分别是两个不合并的二叉树节点和一个合并的二叉树节点使用栈实现二叉树的前序思想来遍历二叉树一整个循环的结束条件是这个栈为空在循环里面判断栈顶元素并让栈顶元素出栈判断栈顶元素前两个元素是否为空来创建此时节点位置合并后的val值随后对左右子树进行处理这里就出现了很大的问题就是我的操作是只要需要合并的两个二叉树其中一个二叉树此位置的节点不为空就会去单独处理这个节点并插入栈这样会浪费很对的时间大致思路就是这样。
递归(把一个子树为空一个子树不为空的情况也考虑进去了过程很多没有必要)
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* dfs(TreeNode* root1, TreeNode* root2) {if(!root1 !root2) return nullptr;TreeNode* root;//处理此节点的val值if(root1 root2) {rootnew TreeNode(root1-valroot2-val);}else if(root1) {rootnew TreeNode(root1-val);}else {rootnew TreeNode(root2-val);}//创建此节点的左右子树if(root1 root2) {root-leftdfs(root1-left,root2-left);root-rightdfs(root1-right,root2-right);}else if(!root1) {root-leftdfs(nullptr,root2-left);root-rightdfs(nullptr,root2-right);}else {root-leftdfs(root1-left,nullptr);root-rightdfs(root1-right,nullptr);}return root;}TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {return dfs(root1,root2);}
};
递推(和上面的代码一样多考虑了一个为空一个不为空的情况)
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {stackpairTreeNode*, TreeNode*st;stackTreeNode*sroot;if(!root1 !root2) return nullptr;TreeNode* rootnew TreeNode();sroot.push(root);st.push({root1, root2});while(!st.empty()) {TreeNode* temp;tempsroot.top();sroot.pop();if(st.top().first st.top().second) {temp-valst.top().first-valst.top().second-val;}else {temp-valst.top().first?st.top().first-val:st.top().second-val;}TreeNode* t1st.top().first;TreeNode* t2st.top().second;st.pop();if (t1 t2) {if(t1-right || t2-right) { st.push({t1-right, t2-right});temp-rightnew TreeNode();sroot.push(temp-right);}if(t1-left || t2-left) {st.push({t1-left, t2-left});temp-leftnew TreeNode();sroot.push(temp-left);}} else if (t1) {if(t1-right) {temp-rightnew TreeNode();sroot.push(temp-right);st.push({t1-right, nullptr});}if(t1-left) {temp-leftnew TreeNode();sroot.push(temp-left);st.push({t1-left, nullptr});}} else if (t2) {if(t2-right) {temp-rightnew TreeNode();sroot.push(temp-right);st.push({nullptr, t2-right});}if(t2-left) {temp-leftnew TreeNode();sroot.push(temp-left);st.push({nullptr, t2-left});}}}return root;}
};
递推优化
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (!root1 !root2) return nullptr;TreeNode* root new TreeNode();stacktupleTreeNode*, TreeNode*, TreeNode* st;st.push({root1, root2, root});while (!st.empty()) {auto [node1, node2, merged] st.top();st.pop();// 节点值合并if (node1 node2)merged-val node1-val node2-val;else if (node1)merged-val node1-val;elsemerged-val node2-val;// 左子节点处理TreeNode* left1 node1 ? node1-left : nullptr;TreeNode* left2 node2 ? node2-left : nullptr;if (left1 || left2) {merged-left new TreeNode();st.push({left1, left2, merged-left});}// 右子节点处理TreeNode* right1 node1 ? node1-right : nullptr;TreeNode* right2 node2 ? node2-right : nullptr;if (right1 || right2) {merged-right new TreeNode();st.push({right1, right2, merged-right});}}return root;}
};
遇到的困难
这道题目我最终的递归和递推都单独处理了空节点会浪费大量时间文档给出的用法就是最简洁的代码文档思路特点就是把root2给添加到root1里如果节点root2的子树root1没有就直接把这一处的整个子树都添加到root1里如果root1里有的子树root2里没有就直接不用管这个子树最后返回root1就完成合并了这样的做法确实代码更加简洁时间复杂度也更加小我当时做到最后都会有发现这个方法。
收获
这道题目本身不难主要是没想到可以直接忽略一个子树为空一个不为空的情况通过这道题目的练习更加体会到了合理正确的思路带来的便捷所以思考思路也是一件非常重要的步骤当时只是一股脑想着遍历二叉树根本没想到会有这种做法。 700.二叉搜索树的搜索 文档讲解代码随想录|700.二叉搜索树的搜索 视频讲解不愧是搜索树这次搜索有方向了| LeetCode700.二叉搜索树中的搜索_哔哩哔哩_bilibili 状态已做出 思路
这道题目只要知道搜索二叉树的特性就能做出来搜索二叉树就是左子树必定比跟节点小右子树比根结点大我这里只写了迭代就是利用循环来遍历搜索二叉树当发现目标值大于节点就遍历这个节点的右子树小于就遍历左子树相等就表示找到了找到空节点就表示没有这个结点。
代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(!root) return nullptr;TreeNode* resultroot;while(result) {if(valresult-val) return result;else if(valresult-val) {resultresult-right;}else {resultresult-left;}}return nullptr;}
};
收获
这道题目主要是熟悉使用二叉搜索树的特性去树中查找需要的节点只要知道搜索二叉树就能马上做出来。 98.验证二叉搜索树 文档讲解代码随想录|98.验证二叉搜索树 视频讲解你对二叉搜索树了解的还不够 | LeetCode98.验证二叉搜索树_哔哩哔哩_bilibili 状态已做出 思路
这道题目让我们判断一颗树是不是二叉搜索树我一开始想到的是递归通过记录子树的最大最小值来来判断是否是搜索树因为二叉搜索树的特点就是左右子树的左子树都必须小于根右子树必须大于根那么就等于是每个节点值大于左子树的最大值小于右子树的最小值就是二叉搜索树了所以我的递归返回值设置为pairpair一个元素记录最小值一个记录最大值在遇到空节点后结束递归并且返回pair类型pair元素一个装INT_MAX一个装INT_MIN这样才能在后面进行正确判断。随后再对左右子树进行判断如果左右子树是空就不做处理非空就判断左子树递归返回的pair最大值是否小于此节点就说明这棵树不是搜索树右子树此时判断最小是是否大于此节点最后返回这个节点的最大值和最小值依次操作最后就能判断出这棵树是否为搜索二叉树了。但是这道题目的优解书文档给出的中序遍历判断文档使用中序给出了递归和迭代两种方式二叉搜索树的特点刚好符合中序遍历的思想因为二叉搜索树是左跟右所以利用中序遍历刚好是从小到大遍历文档使用了变量和指针两种方式来保存上一个遍历的值当下一个值比上一个保存的值小时说明这个二叉树不是搜索树迭代使用栈来模拟中序遍历用一个指针变量来记录上一个遍历的节点最后判断出是否为搜索二叉树。
递归(非中序做法):
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool result true;//递归返回值是队组用来保存子树的最大值和最小值pairint, int dfs(TreeNode* root) {//结束递归并返回队组if (!root) return {INT_MAX, INT_MIN};//先对最大值和最小值的局部变量进行初始化都复制为此节点的val值int minVal root-val;int maxVal root-val;//下面两个if语句判断此节点的左子树和右子树是否符合搜索树if (root-left) {auto left dfs(root-left);if (left.second root-val) result false;minVal min(minVal, left.first);}if (root-right) {auto right dfs(root-right);if (right.first root-val) result false;maxVal max(maxVal, right.second);}return {minVal, maxVal};}bool isValidBST(TreeNode* root) {result true;dfs(root);return result;}
};
遇到的困难
我一开始使用的方法并不是中序遍历没想到可以使用中序来解决但是通过记录最大最小值最后也解决了这道题目主要还是要了解搜索二叉树的特性搜索二叉树并不是单纯的跟大于左小于右而是每个子树都符合这个要求并且左子树的所有节点都要小于跟右子树的左右节点都要大于根这就是判断搜索二叉树的坑如果只是以为左根右就会出现错误中序遍历应该是最符合搜索二叉树的特性的使用这个方式是最好解决的。
收获
虽然这倒题目并没有使用中序遍历来解决但也是通过自己的思路打到的题目要求最后看了文档的方法也了解到了这类题目的优解了解到了搜索二叉树和中序遍历特性相似后续可以使用这种方式来快速解判断是否为二叉搜索树。
