1.4 二叉树的最近公共祖先
题目描述：
解题思路1：
基本思路是通过根节点的左子树和右子树分别找p和q，然后再递归去找。
参考代码：
class Solution { public: bool find(TreeNode* root, TreeNode* x) { if(root==nullptr) return false; if(root==x) return true; return find(root->left,x) || find(root->right,x); } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==nullptr) return nullptr; if(root==p || root==q) return root; bool pInLeft,pInRight,qInLeft,qInRight; pInLeft=find(root->left,p); pInRight=!pInLeft; qInLeft=find(root->left,q); qInRight=!qInLeft; if((pInLeft && qInRight) || (pInRight && qInLeft)) return root; else if(pInLeft && qInLeft) return lowestCommonAncestor(root->left,p,q); else if(pInRight && qInRight) return lowestCommonAncestor(root->right,p,q); else return nullptr; } };
题后反思：
这种方式如果该树大致是一个单叉树时效率就很低下了，这样时间复杂度大概是N^2量级的，有什么更好的解决思路吗？
解题思路2：
我们可以用两个栈来分别存储查找p和q的路径，然后转化为链表相交问题，这样时间复杂度是N量级的。
参考代码：
class Solution { public: //记录路径，最坏情况也是O(N) bool findPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& Path) { if(root==nullptr) return false; Path.push(root);//先把结点入进去 if(root==x) return true; if(findPath(root->left,x,Path))//如果从左子树中找到了就返回 return true; if(findPath(root->right,x,Path))//如果从右子树中找到了就返回 return true; //走到这里说明左子树没有找到，右子树也没有找到，就pop掉栈顶 Path.pop(); return false; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { stack<TreeNode*> pPath; stack<TreeNode*> qPath; findPath(root,p,pPath); findPath(root,q,qPath); //让大的先走差距步 while(pPath.size()!=qPath.size()) { if(pPath.size()>qPath.size()) pPath.pop(); else qPath.pop(); } while(pPath.top()!=qPath.top()) { pPath.pop(); qPath.pop(); } return pPath.top(); } };
运行结果：
1.5 单调栈
题目描述：
解题思路：
单调栈模型，相信大家能够轻松AC.
参考代码：
自己写一个栈：
#include<iostream> using namespace std; const int N=1e5+10; int st[N],tt; int main() { int n; scanf("%d",&n); while(n--) { int x; scanf("%d",&x); while(tt && st[tt]>=x) tt--; if(!tt) printf("-1 "); else printf("%d ",st[tt]); st[++tt]=x; } return 0; }
使用STL中stack:
#include<iostream> #include<stack> using namespace std; int main() { int n; scanf("%d",&n); stack<int> st; while(n--) { int x; scanf("%d",&x); while(!st.empty() && st.top()>=x) st.pop(); if(st.empty()) printf("-1 "); else printf("%d ",st.top()); st.push(x); } return 0; }
2 与队列有关的考题
2.1 二叉树的分层遍历
题目描述：
解题思路：
这种题我们能一眼看出来是用队列做，但是本题的难点在于怎样确定每层结点个数。我们不妨用一个变量levelSize计数每层结点个数，当pop掉该层结点push新的结点后及时更新levelSize。
参考代码：
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> vv; queue<TreeNode*> q; if(root==nullptr) return vv; int levelSize=1; q.push(root); while(!q.empty()) { vector<int> v; while(levelSize--) { TreeNode* front=q.front(); v.push_back(front->val); q.pop(); if(front->left) q.push(front->left); if(front->right) q.push(front->right); } levelSize=q.size(); vv.push_back(v); } return vv; } };
2.2 滑动窗口
题目描述：
解题思路：
这也是一个简单的基础模板题，就直接给大家看代码了。
自己实现一个：
#include<iostream> using namespace std; const int N=1e6+10; int a[N],q[N]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&a[i]); int hh=0,tt=-1; for(int i=0;i<n;i++) { if(hh<=tt && i-m+1>q[hh]) ++hh;//q[hh]不在窗口[i-m,i-1]内就出队 while(hh<=tt && a[i]<=a[q[tt]]) --tt;//当前值<=队尾值，队尾出队（双端队列） q[++tt]=i;//队列中入的是下标目的是为了方便队头出队 if(i-m+1>=0) printf("%d ",a[q[hh]]);//使用队头（最小值） } puts(""); hh=0,tt=-1; for(int i=0;i<n;i++) { if(hh<=tt && i-m+1>q[hh]) ++hh; while(hh<=tt && a[i]>=a[q[tt]]) --tt; q[++tt]=i; if(i-m+1>=0) printf("%d ",a[q[hh]]); } }
采用STL的deque(双端队列):
#include<iostream> #include<deque> using namespace std; const int N=1e6+10; int a[N]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&a[i]); deque<int>q;//双向队列 for(int i=0;i<n;i++) { if(!q.empty() && i-m+1>q.front()) q.pop_front(); while(!q.empty() && a[i]<=a[q.back()]) q.pop_back(); q.push_back(i); if(i-m+1>=0) printf("%d ",a[q.front()]); } puts(""); q.clear();//记得要清理 for(int i=0;i<n;i++) { if(!q.empty() && i-m+1>q.front()) q.pop_front(); while(!q.empty() && a[i]>=a[q.back()]) q.pop_back(); q.push_back(i); if(i-m+1>=0) printf("%d ",a[q.front()]); } return 0; }
