翻轉二叉樹
做法:遞歸即可,注意判斷為空
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if(root==nullptr)return nullptr;TreeNode* node=root->left;root->left=invertTree(root->right);root->right=invertTree(node);return root;}
};
對稱二叉樹
做法一:遞歸。使用兩個不同的指針進入遞歸即可
class Solution {
public:bool check(TreeNode* p,TreeNode* q){if(!p&&!q)return true;if(!p||!q)return false;return p->val==q->val&&check(p->left,q->right)&&check(p->right,q->left);}bool isSymmetric(TreeNode* root) {return check(root->left,root->right);}
};
做法二:迭代。一開始想用deque,但卡在了迭代怎么能讓同一層進行比較,后面看了題解才知道可以直接用queue,只要壓入的時候保證順序即可
class Solution {
public:bool check(TreeNode* u, TreeNode* v) {queue<TreeNode*> q;q.push(u);q.push(v);while(!q.empty()){u=q.front();q.pop();v=q.front();q.pop();if(!u&&!v)continue;if((!u||!v)||(u->val!=v->val))return false;q.push(u->left);q.push(v->right);q.push(u->right);q.push(v->left);}return true;}bool isSymmetric(TreeNode* root) {return check(root->left,root->right);}
};
二叉樹的直徑
做法:一開始想用樹形dp,但發現搞復雜了根本不用。其實最直觀的思想就是,對每個節點依次遍歷,然后求左子樹和右子樹深度,然后進行比較。但我們可以發現,在這一過程中,重復搜索了很多地方。要么記憶化搜索,要么就直接在遞歸中比較即可,這樣就只需要遞歸一次。
class Solution {
public:int ans=0;int depth(TreeNode* root){if(root==nullptr)return 0;int L=depth(root->left);int R=depth(root->right);ans=max(ans,L+R+1);return max(L,R)+1;}int diameterOfBinaryTree(TreeNode* root) {depth(root);return ans-1;}
};
二叉樹的層序遍歷
做法一:迭代,BFS,記錄一下每層的節點個數即可
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if(root==nullptr)return {};vector<vector<int>> vec;queue<TreeNode*>q;q.push(root);while(!q.empty()){vector<int> v;int sz=q.size();for(int i=1;i<=sz;i++){auto u=q.front();q.pop();if(u->left!=nullptr)q.push(u->left);if(u->right!=nullptr)q.push(u->right);v.emplace_back(u->val);}vec.emplace_back(v);} return vec;}
};
做法二:遞歸,這個想法很精妙
class Solution {
private:vector<vector<int>> ret;
public:vector<vector<int>> levelOrder(TreeNode* root) {dfs(root,0);return ret;}void dfs(TreeNode* root,int deep){if(root == nullptr) return;if(deep>=ret.size()) ret.push_back({root->val});else ret[deep].push_back(root->val);dfs(root->left,deep+1);dfs(root->right,deep+1);}
};
將有序數組轉換為二叉搜索樹
做法:每次建立中間節點即可,然后遞歸建立樹
class Solution {
public:TreeNode* build(vector<int>& nums,int left,int right){if(left>right)return nullptr;int mid=(left+right)>>1;TreeNode* root=new TreeNode(nums[mid]);root->left=build(nums,left,mid-1);root->right=build(nums,mid+1,right);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {return build(nums,0,nums.size()-1);}};
驗證二叉搜索樹
做法一:分別dfs兩邊的子樹,如果不滿足條件就返回false
class Solution {
public:bool dfs(TreeNode* root,long long lower,long long upper){if(root==nullptr)return true;if(root->val<=lower||root->val>=upper)return false;return dfs(root->left,lower,root->val)&&dfs(root->right,root->val,upper);}bool isValidBST(TreeNode* root) {return dfs(root,LONG_MIN,LONG_MAX);}
};
做法二:中序遍歷。這里可以遞歸或者不遞歸都可以
class Solution {
public:vector<int> vec;bool flag=true;void dfs(TreeNode* root){if(root==nullptr)return;dfs(root->left);if(vec.size()&&vec.back()>=root->val){flag=false;return;}vec.emplace_back(root->val);dfs(root->right);}bool isValidBST(TreeNode* root) {dfs(root);return flag;}
};
二叉搜索樹中第k小的元素
做法一:非優化。簡單直接的中序遍歷,剛好練一下非遞歸
class Solution {
public:int kthSmallest(TreeNode* root, int k) {int cnt=0;stack<TreeNode*> s;while(root!=nullptr||!s.empty()){if(root!=nullptr){s.push(root);root=root->left;}else{root=s.top();s.pop();cnt++;if(cnt==k)return root->val;root=root->right;}}return -1;}
};
做法二:如果要頻繁訪問第k小的數字,可以通過預處理節點數,有點類似快排找第k個大的
class Solution {
public:unordered_map<TreeNode*,int>nodenum;int countnodenum(TreeNode* node){if(node==nullptr)return 0;nodenum[node]=1+countnodenum(node->left)+countnodenum(node->right);return nodenum[node];}int getnodenum(TreeNode* node){if(node!=nullptr&&nodenum.count(node)){return nodenum[node];}return 0;}int kthSmallest(TreeNode* root, int k) {countnodenum(root);while(root!=nullptr){int left=getnodenum(root->left);if(left<k-1){root=root->right;k-=left+1;}else if(left==k-1)break;else root=root->left;} return root->val;}
};
二叉樹的右視圖
做法一:迭代,廣度優先遍歷即可
class Solution {
public:vector<int> rightSideView(TreeNode* root) {if(root==nullptr)return {};queue<TreeNode*> q;vector<int> vec;q.push(root);while(!q.empty()){int sz=q.size();for(int i=1;i<sz;i++){TreeNode* cur=q.front();q.pop();if(cur->left)q.push(cur->left);if(cur->right)q.push(cur->right);}TreeNode* cur=q.front();q.pop();if(cur->left!=nullptr)q.push(cur->left);if(cur->right!=nullptr)q.push(cur->right);vec.emplace_back(cur->val);}return vec;}
};
做法二:遞歸,其實就和二叉樹層序遍歷那題一樣
class Solution {
public:void bst(TreeNode* node,vector<int>& ans,int depth){if(!node)return;if(depth>ans.size())ans.push_back(node->val);bst(node->right,ans,depth+1);bst(node->left,ans,depth+1);}vector<int> rightSideView(TreeNode* root) {if(!root)return {};vector<int> ans;bst(root,ans,1);return ans;}
};
二叉樹展開為鏈表
做法一:按照前序遍歷的順序來構造鏈表,所以先進行一次前序遍歷,然后用一個vector存下來所有的節點。然后逐步遍歷設置即可
class Solution {
public:void preorder(TreeNode* root,vector<TreeNode*> &vec){if(root){vec.emplace_back(root);preorder(root->left,vec);preorder(root->right,vec);}}void flatten(TreeNode* root) {vector<TreeNode*> vec;preorder(root,vec);int n=vec.size();for(int i=1;i<n;i++){TreeNode* prev=vec[i-1],*cur=vec[i];prev->left=nullptr;prev->right=cur;}}
};
做法二:空間復雜度O(1),對于一個節點,如果左子節點為空,則不需要操作,如果不為空,那么對于右邊,要找到左子樹最右的節點,把右節點連接上去,然后再把左子樹連到右邊即可。非常巧妙的做法
class Solution {
public:void flatten(TreeNode* root) {TreeNode* cur=root;while(cur!=nullptr){if(cur->left!=nullptr){auto next=cur->left;auto predecessor=next;while(predecessor->right!=nullptr)predecessor=predecessor->right;predecessor->right=cur->right;cur->left=nullptr;cur->right=next;}cur=cur->right;}}
};
從前序與中序遍歷序列構造二叉樹
做法一:遞歸,前序遍歷第一個節點是根節點,中序遍歷則是[左子樹,根節點,右子樹],我們可以先根據前序定位根節點,然后根據中序才能知道哪些在左邊,哪些在右邊。遞歸構建即可
class Solution {
public:unordered_map<int,int> mp;TreeNode* build(vector<int>& preorder,vector<int>& inorder,int pl,int pr,int il,int ir){if(pl>pr)return nullptr;int p_root=pl;int in_root=mp[preorder[p_root]];TreeNode* root=new TreeNode(preorder[p_root]);int sz_l=in_root-il;root->left=build(preorder,inorder,pl+1,pl+sz_l,il,in_root-1);root->right=build(preorder,inorder,pl+sz_l+1,pr,in_root+1,ir);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n=preorder.size();for(int i=0;i<n;i++){mp[inorder[i]]=i;}return build(preorder,inorder,0,n-1,0,n-1);}
};
做法二:迭代 先放養,因為肯定會忘記
路徑總和III
做法一:直接遍歷每個節點,對每個節點dfs看有幾個滿足的路徑
class Solution {
public:int rootsum(TreeNode* root,long long target){if(!root)return 0;int ans=0;if(root->val==target)ans++;ans+=rootsum(root->left,target-root->val);ans+=rootsum(root->right,target-root->val);return ans;}int pathSum(TreeNode* root, long long targetSum) {if(!root)return 0;int ans=rootsum(root,targetSum);ans+=pathSum(root->left,targetSum);ans+=pathSum(root->right,targetSum);return ans;}
};
做法二:可以利用前綴和,用哈希表將對應前綴和和數量對應起來。如果遍歷到某一前綴和,前綴和-target的數量就是目前路徑的總和為target的線路。要記得遍歷前哈希加1,遞歸后面要減去1
class Solution {
public:unordered_map<long long,int> pre;int dfs(TreeNode *root,long long cur,int target){if(!root)return 0;int ans=0;cur+=root->val;if(pre.count(cur-target)){ans=pre[cur-target];//哈希表存儲對應值有幾個}pre[cur]++;ans+=dfs(root->left,cur,target);ans+=dfs(root->right,cur,target);pre[cur]--;//因為遍歷完左右子樹就不存在這個前綴和了return ans;}int pathSum(TreeNode* root, int targetSum) {pre[0]=1;return dfs(root,0,targetSum);}
};
二叉樹的最近公共祖先?想起數鏈剖分了
做法一:哈希表
class Solution {
public:unordered_map<int,TreeNode*>fa;unordered_map<int,bool>vis;void dfs(TreeNode* root){if(root->left){fa[root->left->val]=root;dfs(root->left);}if(root->right){fa[root->right->val]=root;dfs(root->right);}}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {fa[root->val]=nullptr;dfs(root);while(p!=nullptr){vis[p->val]=true;p=fa[p->val];}while(q!=nullptr){if(vis[q->val])return q;q=fa[q->val];}return nullptr;}
};
二叉樹中的最大路徑和
做法:由于不能向上面走,所以不是樹形dp。只需要遞歸即可。對于空節點,那么就是貢獻度為0,遞歸的時候,要比較,該節點加左子樹和右子樹的和是否大于maxum,返回的不是和而是節點值加上max(left,right),因為每個節點至多只出現一次
class Solution {
public:int maxSum=INT_MIN;int maxsum(TreeNode* root){if(!root)return 0;int sum=root->val;int leftsum=maxsum(root->left);int rightsum=maxsum(root->right);//maxSum=max(maxSum,leftsum);//maxSum=max(maxSum,rightsum);if(leftsum>0)sum+=leftsum;else leftsum=0;if(rightsum>0)sum+=rightsum;else rightsum=0;maxSum=max(maxSum,sum);return root->val+max(leftsum,rightsum);}int maxPathSum(TreeNode* root) {maxsum(root);return maxSum;}
};
島嶼數量
做法一:深度優先遍歷,搜尋到一個節點,我們可以dfs周邊滿足條件的節點,這樣就能把一整個島嶼全部化為海水。dfs了幾次就代表有幾個島嶼
class Solution {
public:void dfs(vector<vector<char>>& grid,int r,int c){int nr=grid.size();int nc=grid[0].size();grid[r][c]='0';if(r-1>=0&&grid[r-1][c]=='1')dfs(grid,r-1,c);if(r+1<nr&&grid[r+1][c]=='1')dfs(grid,r+1,c);if(c-1>=0&&grid[r][c-1]=='1')dfs(grid,r,c-1);if(c+1<nc&&grid[r][c+1]=='1')dfs(grid,r,c+1);}int numIslands(vector<vector<char>>& grid) {int nr=grid.size();if(!nr)return 0;int nc=grid[0].size();int num=0;for(int r=0;r<nr;r++)for(int c=0;c<nc;c++){if(grid[r][c]=='1'){num++;dfs(grid,r,c);}}return num;}
};
做法二:BFS其實差不多,也是加入pair組成的隊列
做法三:好像能用并查集吧 我不會
腐爛的橘子
做法:BFS
class Solution {
public:int cnt;int dis[10][10];int dir_x[4]={0,1,0,-1};int dir_y[4]={1,0,-1,0};int orangesRotting(vector<vector<int>>& grid) {queue<pair<int,int>>q;cnt=0;int n=grid.size();int m=grid[0].size();for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(grid[i][j]==2){q.push({i,j});//dis[i][j]=0;}else if(grid[i][j]==1){cnt++;}}if(q.empty()&&cnt)return -1;int ans=0;while(!q.empty()){int t=q.size();for(int k=0;k<t;k++){pair<int,int> p=q.front();q.pop();for(int i=0;i<4;i++){int x=p.first+dir_x[i];int y=p.second+dir_y[i];if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]==1){grid[x][y]=2;q.push({x,y});cnt--;}}}if(!q.empty())ans++;}if(cnt)return -1;return ans;}
};
課程表
做法一:拓撲排序
class Solution {
public:int du[2010];unordered_map<int,vector<int>>mp;bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {for(auto cur:prerequisites){du[cur[1]]++;mp[cur[0]].push_back(cur[1]);}queue<int> q;for(int i=0;i<numCourses;i++){if(du[i]==0)q.push(i);}while(!q.empty()){int u=q.front();q.pop();numCourses--;for(auto num:mp[u]){du[num]--;if(du[num]==0)q.push(num);}}if(numCourses==0)return true;return false;}
};