剑指Offer-搜索与回溯算法

剑指 Offer 32 - I. 从上到下打印二叉树

题意：

剑指 Offer 32 - I. 从上到下打印二叉树

解：

BFS板子

代码：

#include<bits/stdc++.h>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<int> levelOrder(TreeNode* root)
{vector<int>ret;if(root==nullptr) return ret; queue<TreeNode*>qe;qe.push(root);while(true){queue<TreeNode*>next;while(!qe.empty()){TreeNode* now=qe.front();qe.pop();ret.push_back(now->val);if(now->left) next.push(now->left);if(now->right) next.push(now->right);}qe=next;if(qe.empty()) break;}return ret;
}
int main()
{return 0;
}

剑指 Offer 32 - II. 从上到下打印二叉树 II

题意：

剑指 Offer 32 - II. 从上到下打印二叉树 II

解：

第一题基础上分层存储=-=

代码：

#include<bits/stdc++.h>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<vector<int>> levelOrder(TreeNode* root)
{vector<vector<int>>ret;if(root==nullptr) return ret; queue<TreeNode*>qe;qe.push(root);while(true){queue<TreeNode*>next;vector<int>temp; while(!qe.empty()){TreeNode* now=qe.front();qe.pop();temp.push_back(now->val);if(now->left) next.push(now->left);if(now->right) next.push(now->right);}ret.push_back(temp);qe=next;if(qe.empty()) break;}return ret;
}
int main()
{return 0;
}

剑指 Offer 32 - III. 从上到下打印二叉树 III

题意：

剑指 Offer 32 - III. 从上到下打印二叉树 III

解：

奇变偶不变

代码：

#include<bits/stdc++.h>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<vector<int>> levelOrder(TreeNode* root)
{vector<vector<int>>ret;bool zt=0;if(root==nullptr) return ret; queue<TreeNode*>qe;qe.push(root);while(true){queue<TreeNode*>next;vector<int>temp; while(!qe.empty()){TreeNode* now=qe.front();qe.pop();temp.push_back(now->val);if(now->left) next.push(now->left);if(now->right) next.push(now->right);}if(zt) reverse(temp.begin(),temp.end());ret.push_back(temp);qe=next;if(qe.empty()) break;zt=!zt;}return ret;
}
int main()
{return 0;
}

剑指 Offer 26. 树的子结构

题意：

剑指 Offer 26. 树的子结构

求树B是不是A的子结构

解：

卡了一下47案例看了半天，原来是判断是否相等Cmp的时候不能看A有没有子节点，而是要看B有没有子节点，铸币了

递归DFS，判断相等，两个函数很像但是初始值不同，有趣的

代码：

#include<iostream>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool myCmp(TreeNode* A, TreeNode* B)
{bool ret=true;if(A==nullptr||B==nullptr) return false;if(A->val!=B->val) return false;if(B->left!=nullptr) ret&=myCmp(A->left,B->left);if(B->right!=nullptr) ret&=myCmp(A->right,B->right);/* WA 47/48if(A->left!=nullptr||B->left!=nullptr) ret&=myCmp(A->left,B->left);if(A->right!=nullptr||B->right!=nullptr) ret&=myCmp(A->right,B->right);*/return ret;
}
bool isSubStructure(TreeNode* A, TreeNode* B)
{if(A==nullptr||B==nullptr) return false;bool ans=false;if(A->val==B->val) ans|=myCmp(A,B);if(ans) return ans;if(A->left!=nullptr) ans|=isSubStructure(A->left,B);if(A->right!=nullptr) ans|=isSubStructure(A->right,B);return ans;
}
int main()
{return 0;
}

剑指 Offer 27. 二叉树的镜像-08

题意：

剑指 Offer 27. 二叉树的镜像

构造镜像树

解：

基本操作

代码：

#include<iostream>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void treeCopy(TreeNode* newRoot,TreeNode* root)
{if(root->left!=nullptr){newRoot->right=new TreeNode(root->left->val);treeCopy(newRoot->right,root->left);}if(root->right!=nullptr){newRoot->left=new TreeNode(root->right->val);treeCopy(newRoot->left,root->right);}
}
TreeNode* mirrorTree(TreeNode* root)
{if(root==nullptr) return nullptr;TreeNode* newRoot=new TreeNode(root->val);treeCopy(newRoot,root);return newRoot;
}
int main()
{return 0;
}

剑指 Offer 28. 对称的二叉树

题意：

剑指 Offer 28. 对称的二叉树

判断是否是对称的二叉树

解：

直接在26题WA代码的基础上改，自己和自己比

代码：

#include<iostream>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool myCmp(TreeNode* A, TreeNode* B)
{bool ret=true;if(A==nullptr||B==nullptr) return false;if(A->val!=B->val) return false;if(A->left!=nullptr||B->right!=nullptr) ret&=myCmp(A->left,B->right);if(A->right!=nullptr||B->left!=nullptr) ret&=myCmp(A->right,B->left);return ret;
}
bool isSymmetric(TreeNode* root)
{if(root==nullptr) return false;bool ans=false;ans|=myCmp(root,root);return ans;
}
int main()
{return 0;
}

剑指 Offer 12. 矩阵中的路径

题意：

剑指 Offer 12. 矩阵中的路径

找字符矩阵中是否有一条线路能构成给定字符串

解：

DFS

代码：

#include<bits/stdc++.h>
using namespace std;
bool check(int i,int j,const vector<vector<bool>>& book,const int& n,const int& m)
{if(i<0||i>=n) return false;if(j<0||j>=m) return false;if(book[i][j]==1) return false;return true;
}
bool dfs(int i,int j,int mao,const vector<vector<char>>& board,vector<vector<bool>>& book,const string& word,const int& n,const int& m)
{bool ans=false;if(mao==word.size()) return true;if(check(i+1,j,book,n,m) && board[i+1][j]==word[mao]){book[i+1][j]=1;ans|=dfs(i+1,j,mao+1,board,book,word,n,m);book[i+1][j]=0;}if(check(i-1,j,book,n,m) && board[i-1][j]==word[mao]){book[i-1][j]=1;ans|=dfs(i-1,j,mao+1,board,book,word,n,m);book[i-1][j]=0;}if(check(i,j+1,book,n,m) && board[i][j+1]==word[mao]){book[i][j+1]=1;ans|=dfs(i,j+1,mao+1,board,book,word,n,m);book[i][j+1]=0;}if(check(i,j-1,book,n,m) && board[i][j-1]==word[mao]){book[i][j-1]=1;ans|=dfs(i,j-1,mao+1,board,book,word,n,m);book[i][j-1]=0;}return ans;
}
bool exist(vector<vector<char>>& board, string word)
{int n=board.size(),m=board[0].size();vector<vector<bool>>book(n,vector<bool>(m));bool ans=false;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(board[i][j]==word[0]){book[i][j]=1;if(ans) break;ans|=dfs(i,j,1,board,book,word,n,m);book[i][j]=0;}}}return ans;
}
int main()
{string word;int n,m;cin>>n>>m;vector<vector<char>> board(n,vector<char>(m));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>board[i][j];}}cin>>word;bool ans=exist(board,word);cout<<boolalpha<<ans<<endl;return 0;
}

剑指 Offer 13. 机器人的运动范围

题意：

剑指 Offer 13. 机器人的运动范围

坐标各位和大于K的格子禁止机器人今日，机器人每次只能走相邻的格子，求有多少个格子可以到达

解：

DFS

代码：

#include<bits/stdc++.h>
using namespace std;
int pointTonum(int i,int j)
{int ret=0;while(i) { ret+=i%10;i/=10; }while(j) { ret+=j%10;j/=10; }return ret;
}
bool check(int i,int j,const int& m,const int& n,const int &k,const vector<vector<bool>>& book)
{if(i<0||i>=m) return false;if(j<0||j>=n) return false;if(book[i][j]==1) return false;return true;
}
void dfs(int&ans,int i,int j,const int& m,const int& n,const int& k,vector<vector<bool>>& book)
{ans++;book[i][j]=1;if(check(i+1,j,m,n,k,book)) dfs(ans,i+1,j,m,n,k,book);if(check(i,j+1,m,n,k,book)) dfs(ans,i,j+1,m,n,k,book);if(check(i-1,j,m,n,k,book)) dfs(ans,i-1,j,m,n,k,book);if(check(i,j-1,m,n,k,book)) dfs(ans,i,j-1,m,n,k,book);
}
int movingCount(int m, int n, int k)
{int ans=0;vector<vector<bool>>book(m,vector<bool>(n));for(int i=0;i<m;i++){for(int j=0;j<n;j++){int t=pointTonum(i,j);if(t>k) book[i][j]=1;}}dfs(ans,0,0,m,n,k,book);return ans;
}
int main()
{int n,m,k;cin>>n>>m>>k;int ans=movingCount(n,m,k);cout<<ans<<endl;return 0; 
}

剑指 Offer 34. 二叉树中和为某一值的路径

题意：

剑指 Offer 34. 二叉树中和为某一值的路径

一条路径需要从根节点到叶子结点，求和为K的所有路径

解：

DFS

代码：

#include<bits/stdc++.h>
using namespace std;
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) {}
};
void dfs(TreeNode* now,int target,vector<vector<int>>& ans,vector<int>temp=vector<int>())
{temp.push_back(now->val);target-=now->val;if(target==0&&now->left==nullptr&&now->right==nullptr){ans.push_back(temp);return;}if(now->left!=nullptr) dfs(now->left,target,ans,temp);if(now->right!=nullptr) dfs(now->right,target,ans,temp);
}
vector<vector<int>> pathSum(TreeNode* root, int target)
{vector<vector<int>>ans;if(root==nullptr) return ans;dfs(root,target,ans);return ans;
}
int main()
{return 0; 
}

剑指 Offer 36. 二叉搜索树与双向链表-09

题意：

剑指 Offer 36. 二叉搜索树与双向链表

将一个二层搜索树变成有序双向链表

解：

中序遍历+链表操作

代码：

#include<bits/stdc++.h>
using namespace std;
class Node {
public:int val;Node* left;Node* right;Node() {}Node(int _val) {val = _val;left = NULL;right = NULL;}Node(int _val, Node* _left, Node* _right) {val = _val;left = _left;right = _right;}
};
Node* head,*last;
void dfs(Node* root)
{if(root->left!=nullptr) dfs(root->left);if(head==nullptr){head=root;last=root;}else{last->right=root;root->left=last;last=root;}if(root->right!=nullptr) dfs(root->right);
}
Node* treeToDoublyList(Node* root)
{if(root==nullptr) return root;dfs(root);head->left=last;last->right=head;return head;
}
int main()
{return 0; 
}

剑指 Offer 54. 二叉搜索树的第k大节点

题意：

剑指 Offer 54. 二叉搜索树的第k大节点

如题

解：

倒序的中序遍历

代码：

#include<iostream>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int dfs(TreeNode* root,int& t,const int& k)
{int ret=0;if(root->left!=nullptr) ret+=dfs(root->left,t,k);t++;if(t==k) return root->val;if(root->right!=nullptr) ret+=dfs(root->right,t,k);
}
int kthLargest(TreeNode* root, int k)
{int t=0;int ans=dfs(root,t,k);return ans;
}
int main()
{return 0;
}

剑指 Offer 55 - I. 二叉树的深度

题意：

剑指 Offer 55 - I. 二叉树的深度

如题

解：

DFS/BFS都行

代码：

#include<iostream>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int dfs(TreeNode* root)
{int ret=0;if(root->left!=nullptr) ret=max(ret,dfs(root->left));if(root->right!=nullptr) ret=max(ret,dfs(root->right));return ret+1;
}
int maxDepth(TreeNode* root)
{if(root==nullptr) return 0;int ans=dfs(root);return ans;
}
int main()
{return 0;
}

剑指 Offer 55 - II. 平衡二叉树

题意：

剑指 Offer 55 - II. 平衡二叉树

判断一颗二叉树是否平衡

解：

DFS，和55差不多，做一个不合法跳出就行

代码：

#include<iostream>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int dfs(TreeNode* root)
{int left=0,right=0;if(root->left!=nullptr) left=dfs(root->left);if(root->right!=nullptr) right=dfs(root->right);if(left==-99||right==-99) return -99;if(abs(left-right)>1) return -99;return max(left,right)+1;
}
bool isBalanced(TreeNode* root)
{if(root==nullptr) return true;int ans=dfs(root);if(ans!=-99) return true;else return false;
}
int main()
{return 0;
}

剑指 Offer 64. 求1+2+…+n

题意：

剑指 Offer 64. 求1+2+…+n

如题，不允许循环和条件

解：

妙用&&的短路现象

代码：

#include<iostream>
using namespace std;
int sumNums(int n)
{int sum=0;n && (sum=n+sumNums(n-1));return sum;
}
int main()
{int n;cin>>n;int ans=sumNums(n);cout<<ans<<endl;return 0;
}

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先-10

题意：

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

给一颗二叉搜索树，和在树中的两个值，求他们的最近公共祖先

解：

对于一个节点，如果两个值一左一右，那么这个值就是他们的最近公共祖先，否则就往那一支里面找

一个节点也可以是它自己的祖先，所以遍历到其中一个的时候就是他们的最近公共祖先

代码：

#include<iostream>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{if(p->val>q->val) swap(p,q);if(root->val==p->val||root->val==q->val) return root;if(root->val>p->val&&root->val<p->val) return root;if(root->val>p->val&&root->val>p->val) return lowestCommonAncestor(root->left,p,q);if(root->val<p->val&&root->val<p->val) return lowestCommonAncestor(root->right,p,q);
}
int main()
{return 0;
}

剑指 Offer 68 - II. 二叉树的最近公共祖先

题意：

剑指 Offer 68 - II. 二叉树的最近公共祖先

给一颗二叉树，和在树中的两个值，求他们的最近公共祖先

解：

不是二叉搜索树，不能直接判断数字是否在左右两边，所以改成dfs获取是否在子树，

然后同样两种情况，1.如果一个节点是p或q，它的子树有一支为真（含p或q）则返回该节点

2.若递归途中有一个节点左右两支均为真，则返回该节点

代码：

#include<iostream>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* ans=nullptr;
bool dfs(TreeNode* root,const TreeNode*const p,const TreeNode*const q)
{if(ans!=nullptr) return false;//已经有答案了 bool ret1=false,ret2=false;if(root->left!=nullptr) ret1|=dfs(root->left,p,q);//左支 if(root->right!=nullptr) ret2|=dfs(root->right,p,q);//右支 if(root==p||root==q)//pq+子树pq {if(ret1||ret2) ans=root;else return true;}if(ret1&&ret2) ans=root;//子树p+子树q //cout<<root->val<<" "<<ret1<<" "<<ret2<<endl;return ret1||ret2;//合并分支信息 }
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{bool temp=dfs(root,p,q);return ans;
}
int main()
{return 0;
}

剑指 Offer 37. 序列化二叉树

题意：

剑指 Offer 37. 序列化二叉树

二叉树变字符串，字符串再变回二叉树

解：

hard题，就是步骤和debug麻烦，写了一坨屎 200ms+ 30mb- 能用就行

代码：

#include<iostream>
using namespace std;
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
string int2string(int x)
{string ret;if(x==0) return "0";while(x){ret=char('0'+x%10)+ret;x/=10;}return ret;
}
int string2int(string s)
{int ret=0;for(auto &ch:s){ret=ret*10+int(ch-'0');}return ret;
}
void node2string(string& s,TreeNode* root)
{s.append(int2string(root->val));if(root->left!=nullptr){s.append(",");node2string(s,root->left);}else s.append(",N");if(root->right!=nullptr){s.append(",");node2string(s,root->right);}else s.append(",N");
}
string serialize(TreeNode* root)
{string tree;if(root==nullptr) return tree;node2string(tree,root);//cout<<"tree:"<<tree<<endl; return tree;
}
void string2node(TreeNode* root,string& data)
{string s;int r=0;while(r<data.size() && data[r]!=',') r++;s=data.substr(0,r);data.erase(0,min(r+1,int(data.size())));if(s=="N") root->left=nullptr;else{root->left=new TreeNode(string2int(s));string2node(root->left,data);}r=0;while(r<data.size() && data[r]!=',') r++;s=data.substr(0,r);data.erase(0,min(r+1,int(data.size())));if(s=="N") root->right=nullptr;else{root->right=new TreeNode(string2int(s));string2node(root->right,data);}
}
TreeNode* deserialize(string data)
{TreeNode* newHead=nullptr;if(data.empty()) return newHead;string s;int r=0;while(r<data.size() && data[r]!=',') r++;s=data.substr(0,r);data.erase(0,min(r+1,int(data.size())));newHead=new TreeNode(string2int(s));string2node(newHead,data);return newHead;
}
int main()
{return 0;
}

剑指 Offer 38. 字符串的排列-11

题意：

剑指 Offer 38. 字符串的排列

输出字符串的全排序（去重）

解：

全排列板子题+set去重

代码：

#include<bits/stdc++.h>
using namespace std;
void qp(int l,string temp,vector<bool>& book,set<string>& ss,const string& s)
{if(l==s.size()){//cout<<"insert:"<<temp<<endl;ss.insert(temp);}for(int i=0;i<s.size();i++){if(book[i]==0){book[i]=1;qp(l+1,temp+s[i],book,ss,s);book[i]=0;}}
}
vector<string> permutation(string s)
{int l=0;int lg=s.length();vector<string>ans;set<string>ss;vector<bool>book(lg);qp(l,"",book,ss,s);for(auto &tempss:ss) ans.push_back(tempss);return ans;
}
int main()
{string s;cin>>s;vector<string>ans=permutation(s);for(auto &a:ans) cout<<a<<endl;return 0;
}