上海松江网站设计公司,青岛公司网站建设开发,请写出网站建设的步骤,安装wordpress主题失败目录栈与队列栈用于匹配的问题队列用于堆二叉树系列深度遍历#xff0c;递归与迭代层序遍历二叉树属性二叉树修改与构造二叉搜索树公共祖先二叉搜索树的修改与构造栈与队列
栈用于匹配的问题
20. 有效的括号 https://leetcode-cn.com/problems/valid-parentheses/ 不匹配的三… 目录栈与队列栈用于匹配的问题队列用于堆二叉树系列深度遍历递归与迭代层序遍历二叉树属性二叉树修改与构造二叉搜索树公共祖先二叉搜索树的修改与构造 栈与队列
栈用于匹配的问题
20. 有效的括号 https://leetcode-cn.com/problems/valid-parentheses/ 不匹配的三种情况; 1、字符串左方向的括号多余了 2、字符串右方向的括号多余了 3、字符串括号没有多余但是类型不匹配。 使用栈的时候三者对应到的栈的情况; 1、已经遍历完字符串但是栈不为空 2、遍历字符串匹配的过程中栈已经为空了 3、再遍历字符串匹配的过程中发现栈中没有要匹配的字符。
class Solution {
public:bool isValid(string s) {stackint st;for(int i 0; i s.size(); i){if(s[i] () st.push());else if(s[i] [) st.push(]);else if(s[i] {) st.push(});//接下来就是判断,这个是1、3情况else if(st.empty() || st.top() ! s[i]){return false;}//如果匹配那么出栈else{st.pop();}}//第2种情况遍历完字符串栈不为空return st.empty();}
};1047. 删除字符串中的所有相邻重复项,与上一题思路一致注意reverse函数的使用。 https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/
class Solution {
public:string removeDuplicates(string s) {stackchar st;for(int i 0; i s.size(); i){if(!st.empty() st.top() s[i]){st.pop();}elsest.push(s[i]);}string result ;//将stack中数据输出while(!st.empty()){result st.top();st.pop();} //然后倒序reverse(result.begin(),result.end());return result;}
};150. 逆波兰表达式求值做计算器程序的肯定知道这个不过一般来说我们编写的是将中缀表达式转换为逆波兰表达式。 逆波兰表达式适合用栈操作运算遇到数字则入栈遇到算符则取出栈顶两个数字进行计算并将结果压入栈中。 与前几题一样思路先将stirng转换成int入栈tokens[i]是运算符使用该运算符计算栈顶前两个元素。 需要注意的编程细节: 1、stack.pop()并不返回栈顶元素。所以要在pop之前取top元素。 2、 stoi(s1)可以将string类型数据转化为int类型比较方便。
class Solution {
public:int evalRPN(vectorstring tokens) {stackint st;for(int i 0; i tokens.size(); i){if(tokens[i] || tokens[i] - || tokens[i] * || tokens[i] /){int num2 st.top();st.pop();int num1 st.top();st.pop();if(tokens[i] ){st.push(num1 num2);}else if(tokens[i] -){st.push(num1 - num2);}else if(tokens[i] *){st.push(num1 * num2);}else{st.push(num1 / num2);}}else{st.push(stoi(tokens[i]));}}return st.top();}
};队列用于堆
347. 前 K 个高频元素思路简单对容器的使用比较复杂。 1、统计元素出现频率使用map 2、对频率进行排序使用优先级队列从队头取元素从队尾添加元素队列内部自动按照元素的权值排序 3、找出前K个高频元素使用小顶堆小顶堆每次将最小的元素弹出最后小顶堆中积累的才是K个最大元素。 构建过程 1、根据频率构建map 2、构建小顶堆将所有频率送入堆中如果堆的大小大于K了将元素从堆顶弹出。 这里需要注意priority_queue的设置方式:
priority_queueType, Container(Type), FunctionalType 就是数据类型Container 就是容器类型Container必须是用数组实现的容器比如vector,deque等等但不能用 list。STL里面默认用的是vectorFunctional 就是比较的方式当需要用自定义的数据类型时才需要传入这三个参数使用基本数据类型时只需要传入数据类型默认是大顶堆. 这里我们设置成这样: 送入的是pair对这里指map比较方式需要自定义这里比较的是pair对第二个元素的值从小到大排序。注意优先队列以vector为容器队首指向vector后面队尾指向vector前面 priority_queue pairint,int,vector pairint,int ,mycomparison pri_que;class Solution {
public://定义优先队列的排序方式,根据pair的第二个元素的大小大的排后面。class mycomparison {public:bool operator()(const pairint,int lhs,const pairint,int rhs) {return lhs.second rhs.second;}};vectorint topKFrequent(vectorint nums, int k) {//统计元素出现频率unordered_mapint,int map; //mapnums[i],对应频次for(int i 0; i nums.size(); i)map[nums[i]];//对频率排序//定义一个小顶堆大小为kpriority_queue pairint,int,vector pairint,int ,mycomparison pri_que;//用固定大小k的小顶堆扫描所有频率的数值for(unordered_mapint,int::iterator it map.begin(); it ! map.end(); it){pri_que.push(*it);if(pri_que.size() k) pri_que.pop();}//找出前k个高频元素因为小顶堆先弹出的是最小的所以倒序输出到数组中。vectorint result(k);for(int i k - 1; i 0; i--){result[i] pri_que.top().first;pri_que.pop();}return result;}
};二叉树系列
二叉树链式存储方式
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};深度遍历递归与迭代
三种遍历方式: 144. 二叉树的前序遍历 https://leetcode-cn.com/problems/binary-tree-preorder-traversal/ 145. 二叉树的后序遍历 https://leetcode-cn.com/problems/binary-tree-postorder-traversal/ 94. 二叉树的中序遍历 https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
递归法模板前序遍历为例
class Solution {
public:void traversal(TreeNode* cur,vectorint vec){if(cur nullptr) return;vec.push_back(cur-val);traversal(cur-left,vec);traversal(cur-right,vec);}vectorint preorderTraversal(TreeNode* root) {vectorint result;traversal(root,result);return result;}
};迭代法模板中序遍历为例 注意栈的特性入栈和出栈相反所以如果想输出顺序为“左中右”入栈顺序必须为“右中左”
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* st;if(root ! nullptr) st.push(root);while(!st.empty()){TreeNode* node st.top();if(node ! nullptr){st.pop();if(node-right ! nullptr) st.push(node-right);st.push(node);st.push(nullptr);if(node-left ! nullptr) st.push(node-left);}else{st.pop();result.push_back(st.top()-val);st.pop();}}return result;}
};层序遍历
层序遍历模板如下:
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* que;if(root ! nullptr) que.push(root);vectorvectorint result;while(!que.empty()) {int size que.size();vectorint vec;for(int i 0; i size; i){TreeNode* node que.front();que.pop();vec.push_back(node-val);if(node-left) que.push(node-left);if(node-right) que.push(node-right);}result.push_back(vec);}return result;}
};102. 二叉树的层序遍历 https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ 107. 二叉树的层序遍历 II https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/ 199. 二叉树的右视图 https://leetcode-cn.com/problems/binary-tree-right-side-view/ 637. 二叉树的层平均值 https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/ 429. N 叉树的层序遍历 https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/ 515. 在每个树行中找最大值注意max初始值取最小值INT_MIN https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/ 116. 填充每个节点的下一个右侧节点指针,这一题要注意同层节点之间的链接在单层遍历的时候记录本层的头部节点然后在遍历的时候让前一个节点指向本节点本层最后一个节点next指向nullptr。 117. 填充每个节点的下一个右侧节点指针 II这两题代码一样。 https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/ https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
class Solution {
public:Node* connect(Node* root) {queueNode* que;if(root ! nullptr) que.push(root);while(!que.empty()){int size que.size();Node* pre;Node* now;for(int i 0; i size; i){//每层第一个元素if(i 0){pre que.front();que.pop();now pre;}else //非第一个元素{now que.front();que.pop();pre-next now;pre now;}if(now-left) que.push(now-left);if(now-right) que.push(now-right);}//每一层最后一个元素pre-next nullptr;}return root;}
};104. 二叉树的最大深度层序遍历,在while循环中 https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/ 111. 二叉树的最小深度,一样的思路不过在每层节点遍历时需要检查是否无左右孩子如果没有则立刻返回当前层数。
if(!node-left !node-right) return result;二叉树属性
101. 对称二叉树 https://leetcode-cn.com/problems/symmetric-tree/ 递归法外层是对称的内层也是对称的。 确定递归函数参数、返回值
bool compare(TreeNode* left,TreeNode* right)确定终止条件 1、左右都为空返回true 2、左右只有一个为空返回false 3、左右结点均不为空比较结点数值不相同返回false 4、左右结点均不为空数值相同时还要继续向下判断 确定单层逻辑; 1、比较二叉树外侧是否对称传入左结点的左孩子右结点的右孩子。 2、比较内侧是否对称传入左结点的右孩子右结点的左孩子。 3、如果左右都对称就返回true否则返回false
class Solution {
public:bool compare(TreeNode* left,TreeNode* right){if(!left !right) return true;else if((!left right) || (left !right)) return false;else if(right-val ! left-val) return false;//下面就是right-val left-val的情况了还得继续探讨bool outside compare(right-right,left-left);bool inside compare(right-left,left-right);return (outside inside);}bool isSymmetric(TreeNode* root) {if(root nullptr) return true;return compare(root-left,root-right);}
};关于二叉树的最小深度与最大深度在层序遍历中已经涉及到了 …在此省略 222. 完全二叉树的节点个数,层序遍历节点计数 https://leetcode-cn.com/problems/count-complete-tree-nodes/ 110. 平衡二叉树 https://leetcode-cn.com/problems/balanced-binary-tree/ 递归三部曲 1、确定递归函数的参数和返回值 传入当前节点返回值为当前节点的高度。返回-1表示不是平衡二叉树 2、终止条件 遇到空节点为终止返回0表示当前节点为根节点的高度为0 3、单层的逻辑 判断当前传入节点为根节点的二叉树是否为平衡二叉树比较左子树高度和右子树高度差值1返回当前二叉树的高度否则返回-1.
class Solution {
public:int getDepth(TreeNode* node){if(node nullptr) return 0;int leftDepth getDepth(node-left);if(leftDepth -1) return -1;int rightDepth getDepth(node-right);if(rightDepth -1) return -1;int result;if(abs(leftDepth - rightDepth) 1)return -1;elseresult 1 max(leftDepth,rightDepth);return result;}bool isBalanced(TreeNode* root) {if(getDepth(root) ! -1) return true;else return false;}
};257. 二叉树的所有路径 递归三部曲前序遍历回溯pop字符串处理即可。
class Solution {
public:void traversal(TreeNode* cur, vectorint path,vectorstring result){path.push_back(cur-val);//到达叶子节点if(cur-left nullptr cur-right nullptr){string sPath;for(int i 0; i path.size() - 1; i){sPath to_string(path[i]);sPath -;}sPath to_string(path[path.size() - 1]);result.push_back(sPath);return;}//如果不是叶子节点if(cur-left){traversal(cur-left,path,result);path.pop_back(); //回溯}if(cur-right){traversal(cur-right,path,result);path.pop_back(); //回溯}}vectorstring binaryTreePaths(TreeNode* root) {vectorstring result;vectorint path;if(root nullptr) return result;traversal(root,path,result);return result;}
};404. 左叶子之和 https://leetcode-cn.com/problems/sum-of-left-leaves/ 如果某节点的左节点不为空且左节点没有左右孩子那么这个节点就是左叶子。 必须通过节点的父节点来判断其左孩子是不是左叶子。 递归三部曲 1、返回值为数值之和传入参数为树的根节点 2、终止条件遇到空节点返回 3、单层逻辑遇到左叶子节点的时候记录数值然后通过递归求取左子树左叶子之和和右子树左子叶之和相加便是整个树的左叶子之和。
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if(root nullptr) return 0;int leftval sumOfLeftLeaves(root-left);int rightval sumOfLeftLeaves(root-right);int midval 0;if(root-left ! nullptr root-left-left nullptr root-left-right nullptr){midval root-left-val;}int sum midval leftval rightval;return sum;}
};513. 找树左下角的值 https://leetcode-cn.com/problems/find-bottom-left-tree-value/ 层序遍历记录每一行的第一个节点数值即可。 112. 路径总和 https://leetcode-cn.com/problems/path-sum/ 递归三部曲 1、参数二叉树的根节点一个计数器 这个计数器用来计算二叉树的一条边之和是否正好是目标和计数器为int 返回值bool 2、终止条件 count初始值为目标和然后每次减去遍历路径点的数值。 如果最后count 0同时到了叶子节点的话说明找到了目标和。 3、单层逻辑 由于终止条件是判断叶子节点所以递归的过程中不要让空节点进入递归。 如果递归函数的返回值为true说明找到了合适的路径应该立即返回。
class Solution {
public:bool traversal(TreeNode* cur,int count){if(cur-left nullptr cur-right nullptr count 0) return true; //遇到叶子节点并且计数为0if(cur-left nullptr cur-right nullptr) return false; //遇到叶子节点而没有找到合适的边直接返回if(cur-left) {count - cur-left-val;if(traversal(cur-left,count)) return true;count cur-left-val;}if(cur-right) {count - cur-right-val;if(traversal(cur-right,count)) return true;count cur-right-val;}//否则return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(root nullptr) return false;targetSum targetSum - root-val;return traversal(root,targetSum);}
};二叉树修改与构造
226. 翻转二叉树 先序遍历先交换左右孩子然后反转左子树反转右子树。
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root nullptr) return root;swap(root-left,root-right);invertTree(root-left);invertTree(root-right);return root;}
};106. 从中序与后序遍历序列构造二叉树 比较复杂 https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 步骤 1、如果数组大小为0的话说明是空节点 2、如果不为空取后序数组最后一个元素作为节点元素 3、找到后序数组最后一个元素在中序数组的位置作为切割点 4、切割中序数组切成中序左数组和中序右数组。记住先切割中序数组 5、切割后序数组切成后序左数组和后序右数组 6、递归处理左区间和右区间
切割的时候按照左闭右开的原则。后序数组的切割要根据中序数组切割出来的大小还要注意后序数组在切割前要将最后一个数剔除。
class Solution {
public:TreeNode* traversal(vectorint inorder,int Inbegin,int Inend,vectorint postorder,int Postbegin,int Postend){//第一步,检查后序数组大小if(Postbegin Postend) return nullptr;//第二步后序数组中最后一个元素就是当前的中间节点int rootval postorder[Postend - 1];TreeNode* root new TreeNode(rootval);//叶子节点if(Postbegin - Postend 1) return root;//第三步中序数组找切割点int splitIndex 0;for(splitIndex Inbegin; splitIndex Inend; splitIndex){if(inorder[splitIndex] rootval) break;}//第四步切割中序数组得到中序左数组和中序右数组int leftInbegin Inbegin;int leftInend splitIndex;int rightInbegin splitIndex1;int rightInend Inend;//第五步切割后序数组得到后序左数组和后序右数组int leftPostbegin Postbegin;int leftPostend Postbegin leftInend - leftInbegin;int rightPostbegin leftPostend;int rightPostend Postend - 1;//第六步递归处理左区间和右区间root-left traversal(inorder,leftInbegin,leftInend,postorder,leftPostbegin,leftPostend);root-right traversal(inorder,rightInbegin,rightInend,postorder,rightPostbegin,rightPostend);return root;} TreeNode* buildTree(vectorint inorder, vectorint postorder) {if(inorder.size() 0 || postorder.size() 0) return nullptr;//左闭右开return traversal(inorder,0,inorder.size(),postorder,0,postorder.size());}
};105. 从前序与中序遍历序列构造二叉树,操作类似 https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/ 654. 最大二叉树 https://leetcode-cn.com/problems/maximum-binary-tree/submissions/
二叉搜索树
700. 二叉搜索树中的搜索 递归 TreeNode* searchBST(TreeNode* root, int val) {if(root nullptr || root-val val) return root;if(root-val val) return searchBST(root-left,val);if(root-val val) return searchBST(root-right,val);return nullptr;}98. 验证二叉搜索树 二叉搜索树中序遍历得到的数组是递增的。
class Solution {
public:vectorint vec;void traversal(TreeNode* node){if(node nullptr) return ;traversal(node-left);vec.push_back(node-val);traversal(node-right);}bool isValidBST(TreeNode* root) {vec.clear();traversal(root);for(int i 1; i vec.size(); i){if(vec[i] vec[i - 1]) return false;}return true;}
};530. 二叉搜索树的最小绝对差 转换为有序数组然后对有序数组进行比较。 501. 二叉搜索树中的众数 转换为有序数组然后对相邻两个元素进行比较统计相同频次有一些细节需要注意。
class Solution {
public:vectorint vec;void traversal(TreeNode* node){if(node nullptr) return ;traversal(node-left);vec.push_back(node-val);traversal(node-right);}vectorint findMode(TreeNode* root) {if(root nullptr) return {};vec.clear();vectorint result;traversal(root);unordered_mapint,int umap;int maxcount 1;int count 1;result.push_back(vec[0]);for(int i 1; i vec.size(); i){if(vec[i] vec[i-1]){count;}elsecount 1;if(count maxcount)result.push_back(vec[i]);if(count maxcount){maxcount count;result.clear();result.push_back(vec[i]);}}return result;}
};538. 把二叉搜索树转换为累加树 https://leetcode-cn.com/problems/convert-bst-to-greater-tree/ 定义一个全局变量preval用来存储上一个节点值然后右中左遍历二叉树。中间节点处理就是加上preaval然后更新preval。
公共祖先
236. 二叉树的最近公共祖先 https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/ 通过后序遍历回溯自下向上。 如何判断一个节点是节点q和节点p的公共祖先 如果找到一个节点发现左子树出现了节点p右子树出现了q或者左子树出现q右子树出现p。那么该节点就是节点p和q的最近公共祖先。
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root p || root q || root nullptr) return root;TreeNode* left lowestCommonAncestor(root-left,p,q);TreeNode* right lowestCommonAncestor(root-right,p,q);//如果left和right都不为空则说明root就是最近公共祖先if(left ! nullptr right ! nullptr) return root;if(left nullptr right ! nullptr) return right;else if(left ! nullptr right nullptr) return left;else return nullptr;}
};235. 二叉搜索树的最近公共祖先 https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/submissions/
class Solution {
public:TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q){if(cur nullptr) return cur;if(cur-val p-val cur-val q-val) {TreeNode* left traversal(cur-left,p,q);if(left ! nullptr) return left;}if(cur-val p-val cur-val q-val){TreeNode* right traversal(cur-right,p,q);if(right ! nullptr) return right;}//否则说明cur是最近公共祖先从底向上return cur;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root,p,q);}
};二叉搜索树的修改与构造
701. 二叉搜索树中的插入操作 https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/ 遍历二叉搜索树然后遇到空节点插入即可。递归函数返回节点。
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if(root nullptr){//插入操作TreeNode* node new TreeNode(val);return node;}if(root-val val) root-left insertIntoBST(root-left,val);if(root-val val) root-right insertIntoBST(root-right,val);return root; }
};450. 删除二叉搜索树中的节点 https://leetcode-cn.com/problems/delete-node-in-a-bst/ 删除操作比较麻烦 1、没有找到删除的结点遍历到空结点直接返回。 2、找到了删除的结点 【1】如果左右孩子都为空直接删除这个结点返回NULL为根结点 【2】如果左孩子为空右孩子不为空删除结点右孩子补位返回右孩子作为根结点 【3】如果右孩子为空左孩子不为空删除结点左孩子补位返回左孩子作为根结点 【4】如果左右孩子不为空则将删除结点的左子树的头结点放到删除结点的右子树的最左边结点的左孩子上返回删除结点右孩子作为新的结点
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(root nullptr) return root;//如果找到了该节点if(root-val key) {//第二种情况左右孩子均空删除该节点返回nullptrif(root-right nullptr root-left nullptr) return nullptr;if(root-left nullptr) return root-right;else if(root-right nullptr) return root-left;else{TreeNode* cur root-right; //找右子树最左边节点while(cur-left ! nullptr)cur cur-left;cur-left root-left;TreeNode* tmp root;root root-right;delete tmp;return root;}}//如果没有找到继续遍历if(root-val key) root-left deleteNode(root-left,key);if(root-val key) root-right deleteNode(root-right,key);return root;}
};669. 修剪二叉搜索树 https://leetcode-cn.com/problems/trim-a-binary-search-tree/ 如果当前结点的值小于low要对该结点的右孩子进行再次搜索直到找到满足区间的结点或者空结点最后返回right结点 如果当前结点的值大于high要对该结点的左孩子进行再次搜索直到找到满足区间的结点或者空结点最后返回left结点。 自上而下遍历检查直到整棵树遍历完。 依次遍历结点左右孩子并将返回的结果作为当前结点的左右孩子。 最后返回当前结点。 返回的结点必然是val在区间内或者是空结点。
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);return right;}if(root-val high){TreeNode* left trimBST(root-left,low,high);return left;}//如果在这个区间内那么就对左右子树进行操作root-left trimBST(root-left,low,high);root-right trimBST(root-right,low,high);return root;}
};108. 修剪二叉搜索树 https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/\
class Solution {
public:TreeNode* traversal(vectorint nums,int left,int right){//这里我们定义区间是左闭右开的if(left right) return nullptr;int mid left ((right-left) 1);TreeNode* node new TreeNode(nums[mid]);node-left traversal(nums,left,mid);node-right traversal(nums,mid1,right);return node;}TreeNode* sortedArrayToBST(vectorint nums) {if(nums.empty()) return nullptr;return traversal(nums,0,nums.size());}
};
