1.反转链表
迭代版本:
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre=NULL,*cur=head;
while(cur)
{
auto next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
return pre;
}
};
递归版本:注意这个函数的意义即可，他的操作是将链表反转过来，并且返回的是尾结点
class Solution {
public:
ListNode* reverseList(ListNode* head) {
while(!head||!head->next) return head;
auto tail=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return tail;
}
};
2.合并两个链表
采用归并排序的思想，逐个比较然后添加
class Solution {
public:
ListNode* merge(ListNode* l1, ListNode* l2) {
auto dummy=new ListNode(-1);
auto cur=dummy;
while(l1&&l2)
{
if(l1->val<l2->val)
{
cur->next=l1;
cur=l1;
l1=l1->next;
}
else
{
cur->next=l2;
cur=l2;
l2=l2->next;
}
}
if(l1)cur->next=l1;
else if(l2)cur->next=l2;
return dummy->next;
}
};
3.树的子结构
class Solution {
public:
bool hasSubtree(TreeNode* pRoot1,TreeNode* pRoot2) {
if(!pRoot1||!pRoot2) return false;
if(ispart(pRoot1,pRoot2)) return true;
return hasSubtree(pRoot1->left,pRoot2)||hasSubtree(pRoot1->right,pRoot2);
}
bool ispart(TreeNode* pRoot1,TreeNode* pRoot2)
{
if(!pRoot2)return true;
if(!pRoot1||pRoot1->val!=pRoot2->val) return false;
return ispart(pRoot1->left,pRoot2->left)&&ispart(pRoot1->right,pRoot2->right);
}
};
4.二叉树的镜像
class Solution {
public:
void mirror(TreeNode* root) {
if(!root) return ;
mirror(root->left);
mirror(root->right);
swap(root->left,root->right);
}
};
5.对称的二叉树
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root) return true;
return dfs(root->left,root->right);
}
bool dfs(TreeNode* p,TreeNode* q)
{
if(!p||!q)return !p&&!q;
if(p->val!=q->val) return false;
return dfs(p->left,q->right)&&dfs(p->right,q->left);
}
};
6.顺时针打印矩阵
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
vector<int>vt;
if(matrix.empty()||matrix[0].size()==0)return vt;
int n=matrix.size(),m=matrix[0].size();
int book[n+5][m+5];
memset(book,0,sizeof book);
int tol=1,x=0,y=0;
book[0][0]=1;
vt.push_back(matrix[0][0]);
while(tol<n*m)
{
while(y+1<m&&book[x][y+1]==0)
{
vt.push_back(matrix[x][++y]);
tol++;
book[x][y]=1;
}
while(x+1<n&&book[x+1][y]==0)
{
vt.push_back(matrix[++x][y]);
tol++;
book[x][y]=1;
}
while(y-1>=0&&book[x][y-1]==0)
{
vt.push_back(matrix[x][--y]);
tol++;
book[x][y]=1;
}
while(x-1>=0&&book[x-1][y]==0)
{
vt.push_back(matrix[--x][y]);
tol++;
book[x][y]=1;
}
}
return vt;
}
};
7.包含main的栈
class MinStack {
public:
stack<int>stk,min_stk;
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
if(stk.empty()|| min_stk.top()>=x)min_stk.push(x);
stk.push(x);
}
void pop() {
if(stk.top()==min_stk.top())min_stk.pop();
stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return min_stk.top();
}
};
8.栈的压入、弹出序列
class Solution {
public:
bool isPopOrder(vector<int> pushV,vector<int> popV) {
if(pushV.size()!=popV.size()) return false;
stack<int>st;
int i=0;
for(auto x:pushV)
{
st.push(x);
while(st.size()&&st.top()==popV[i])
{
st.pop();
i++;
}
}
return st.empty();
}
};
9.不分行从上往下打印二叉树
层序遍历板子题
class Solution {
public:
vector<int> printFromTopToBottom(TreeNode* root) {
queue<TreeNode*>q;
vector<int>vt;
if(!root)return vt;
q.push(root);
while(!q.empty())
{
TreeNode* top=q.front();
q.pop();
vt.push_back(top->val);
if(top->left)q.push(top->left);
if(top->right)q.push(top->right);
}
return vt;
}
};
10.分行从上往下打印二叉树
通过记录队列长度达到分层的目的
class Solution {
public:
vector<vector<int>> printFromTopToBottom(TreeNode* root) {
queue<TreeNode*>q;
vector<vector<int>>res;
if(!root) return res;
q.push(root);
while(!q.empty())
{
vector<int>cur;
int n=q.size();//每次统计队列中的个数来做到分层
for(int i=0;i<n;i++)
{
auto top=q.front();
q.pop();
cur.push_back(top->val);
if(top->left)q.push(top->left);
if(top->right)q.push(top->right);
}
res.push_back(cur);
}
return res;
}
};
11.之字形打印二叉树
class Solution {
public:
vector<vector<int>> printFromTopToBottom(TreeNode* root) {
int book=1;
queue<TreeNode*>q;
vector<vector<int>>res;
if(!root)return res;
q.push(root);
while(!q.empty())
{
int n=q.size();
vector<int>vt;
for(int i=0;i<n;i++)
{
auto top=q.front();
q.pop();
vt.push_back(top->val);
if(top->left)
q.push(top->left);
if(top->right)
q.push(top->right);
}
if(book==1)
res.push_back(vt);
else
{
reverse(vt.begin(),vt.end());
res.push_back(vt);
}
book=-book;
}
return res;
}
};
