Leetcode hot 100(day 4)

翻转二叉树
做法：递归即可，留意判断为空

2. class Solution {
3. public:
4.     TreeNode* invertTree(TreeNode* root) {
5.         if(root==nullptr)return nullptr;
6.         TreeNode* node=root->left;
7.         root->left=invertTree(root->right);
8.         root->right=invertTree(node);
9.         return root;
10.     }
11. };

复制代码

---

对称二叉树
做法一：递归。使用两个不同的指针进入递归即可

2. class Solution {
3. public:
4.     bool check(TreeNode* p,TreeNode* q)
5.     {
6.         if(!p&&!q)return true;
7.         if(!p||!q)return false;
8.         return p->val==q->val&&check(p->left,q->right)&&check(p->right,q->left);
9.     }
10.     bool isSymmetric(TreeNode* root) {
11.         return check(root->left,root->right);
12.     }
13. };

复制代码

做法二：迭代。一开始想用deque，但卡在了迭代怎么能让同一层进行比力，后面看了题解才知道可以直接用queue，只要压入的时间保证次序即可

2. class Solution {
3. public:
4.     bool check(TreeNode* u, TreeNode* v) {
5.         queue<TreeNode*> q;
6.         q.push(u);
7.         q.push(v);
8.         while(!q.empty())
9.         {
10.             u=q.front();
11.             q.pop();
12.             v=q.front();
13.             q.pop();
14.             if(!u&&!v)continue;
15.             if((!u||!v)||(u->val!=v->val))return false;
16.             q.push(u->left);
17.             q.push(v->right);
18.             q.push(u->right);
19.             q.push(v->left);
20.         }
21.         return true;
22.     }
23.     bool isSymmetric(TreeNode* root) {
24.         return check(root->left,root->right);
25.     }
26. };

复制代码

---

二叉树的直径
做法：一开始想用树形dp，但发现搞复杂了根本不用。实在最直观的思想就是，对每个节点依次遍历，然后求左子树和右子树深度，然后进行比力。但我们可以发现，在这一过程中，重复搜刮了很多地方。要么影象化搜刮，要么就直接在递归中比力即可，如许就只必要递归一次。

2. class Solution {
3. public:
4.     int ans=0;
5.     int depth(TreeNode* root)
6.     {
7.         if(root==nullptr)return 0;
8.         int L=depth(root->left);
9.         int R=depth(root->right);
10.         ans=max(ans,L+R+1);
11.         return max(L,R)+1;
12.     }
13.     int diameterOfBinaryTree(TreeNode* root) {
14.         depth(root);
15.         return ans-1;
17.     }
18. };

复制代码

---

二叉树的层序遍历
做法一：迭代，BFS，记录一下每层的节点个数即可

2. class Solution {
3. public:
4.     vector<vector<int>> levelOrder(TreeNode* root) {
5.         if(root==nullptr)return {};
6.         vector<vector<int>> vec;
7.         queue<TreeNode*>q;
8.         q.push(root);
9.         while(!q.empty())
10.         {
11.             vector<int> v;
12.             int sz=q.size();
13.             for(int i=1;i<=sz;i++)
14.             {
15.                 auto u=q.front();
16.                 q.pop();
17.                 if(u->left!=nullptr)q.push(u->left);
18.                 if(u->right!=nullptr)q.push(u->right);
19.                 v.emplace_back(u->val);
20.             }
21.             vec.emplace_back(v);
22.         }        
23.         return vec;
24.     }
25. };

复制代码

做法二：递归，这个想法很精妙

2. class Solution {
3. private:
4.     vector<vector<int>> ret;
5. public:
6.     vector<vector<int>> levelOrder(TreeNode* root) {
7.         dfs(root,0);
8.         return ret;
9.     }
10.     void dfs(TreeNode* root,int deep)
11.     {
12.         if(root == nullptr) return;
13.         if(deep>=ret.size()) ret.push_back({root->val});
14.         else ret[deep].push_back(root->val);
15.         dfs(root->left,deep+1);
16.         dfs(root->right,deep+1);
17.     }
18. };

复制代码

---

将有序数组转换为二叉搜刮树
做法：每次建立中间节点即可，然后递归建立树

2. class Solution {
3. public:
4.     TreeNode* build(vector<int>& nums,int left,int right)
5.     {
6.         if(left>right)return nullptr;
7.         int mid=(left+right)>>1;
8.         TreeNode* root=new TreeNode(nums[mid]);
9.         root->left=build(nums,left,mid-1);
10.         root->right=build(nums,mid+1,right);
11.         return root;
12.     }
13.     TreeNode* sortedArrayToBST(vector<int>& nums) {
14.         return build(nums,0,nums.size()-1);
15.     }
17. };

复制代码

---

验证二叉搜刮树
做法一：分别dfs两边的子树，如果不满意条件就返回false

2. class Solution {
3. public:
4.     bool dfs(TreeNode* root,long long lower,long long upper)
5.     {
6.         if(root==nullptr)return true;
7.         if(root->val<=lower||root->val>=upper)return false;
8.         return dfs(root->left,lower,root->val)&&dfs(root->right,root->val,upper);
9.     }
10.     bool isValidBST(TreeNode* root) {
11.         return dfs(root,LONG_MIN,LONG_MAX);
12.     }
13. };

复制代码

做法二：中序遍历。这里可以递归大概不递归都可以

2. class Solution {
3. public:
4.     vector<int> vec;
5.     bool flag=true;
6.     void dfs(TreeNode* root)
7.     {
8.         if(root==nullptr)return;
9.         dfs(root->left);
10.         if(vec.size()&&vec.back()>=root->val)
11.         {
12.             flag=false;
13.             return;
14.         }
15.         vec.emplace_back(root->val);
16.         dfs(root->right);
17.     }
18.     bool isValidBST(TreeNode* root) {
19.         dfs(root);
20.         return flag;
21.     }
22. };

复制代码

---

二叉搜刮树中第k小的元素
做法一：非优化。简单直接的中序遍历，刚好练一下非递归

2. class Solution {
3. public:
4.     int kthSmallest(TreeNode* root, int k) {
5.         int cnt=0;
6.         stack<TreeNode*> s;
7.         while(root!=nullptr||!s.empty())
8.         {
9.             if(root!=nullptr)
10.             {
11.                 s.push(root);
12.                 root=root->left;
13.             }
14.             else
15.             {
16.                 root=s.top();
17.                 s.pop();
18.                 cnt++;
19.                 if(cnt==k)return root->val;
20.                 root=root->right;
21.             }
22.         }
23.         return -1;
24.     }
25. };

复制代码

做法二：如果要频繁访问第k小的数字，可以通过预处理节点数，有点雷同快排找第k个大的

2. class Solution {
3. public:
4.     unordered_map<TreeNode*,int>nodenum;
5.     int countnodenum(TreeNode* node)
6.     {
7.         if(node==nullptr)return 0;
8.         nodenum[node]=1+countnodenum(node->left)+countnodenum(node->right);
9.         return nodenum[node];
10.     }
11.     int getnodenum(TreeNode* node)
12.     {
13.         if(node!=nullptr&&nodenum.count(node))
14.         {
15.             return nodenum[node];
16.         }
17.         return 0;
18.     }
19.    
20.     int kthSmallest(TreeNode* root, int k) {
21.         countnodenum(root);
22.         while(root!=nullptr)
23.         {
24.             int left=getnodenum(root->left);
25.             if(left<k-1)
26.             {
27.                 root=root->right;
28.                 k-=left+1;
29.             }
30.             else if(left==k-1)break;
31.             else root=root->left;
32.         }   
33.         return root->val;
34.     }
35. };

复制代码

---

二叉树的右视图
做法一：迭代，广度优先遍历即可

2. class Solution {
3. public:
4.     vector<int> rightSideView(TreeNode* root) {
5.         if(root==nullptr)return {};
6.         queue<TreeNode*> q;
7.         vector<int> vec;
8.         q.push(root);
9.         while(!q.empty())
10.         {
11.             int sz=q.size();
12.             for(int i=1;i<sz;i++)
13.             {
14.                 TreeNode* cur=q.front();
15.                 q.pop();
16.                 if(cur->left)q.push(cur->left);
17.                 if(cur->right)q.push(cur->right);
18.             }
19.             TreeNode* cur=q.front();
20.             q.pop();
21.             if(cur->left!=nullptr)q.push(cur->left);
22.             if(cur->right!=nullptr)q.push(cur->right);
23.             vec.emplace_back(cur->val);
24.         }
25.         return vec;
26.     }
27. };

复制代码

做法二：递归，实在就和二叉树层序遍历那题一样

2. class Solution {
3. public:
4.     void bst(TreeNode* node,vector<int>& ans,int depth)
5.     {
6.         if(!node)return;
7.         if(depth>ans.size())ans.push_back(node->val);
8.         bst(node->right,ans,depth+1);
9.         bst(node->left,ans,depth+1);
10.     }
11.     vector<int> rightSideView(TreeNode* root) {
12.         if(!root)return {};
13.         vector<int> ans;
14.         bst(root,ans,1);
15.         return ans;
16.     }
17. };

复制代码

---

二叉树展开为链表
做法一：按照前序遍历的次序来构造链表，以是先进行一次前序遍历，然后用一个vector存下来所有的节点。然后逐步遍历设置即可

2. class Solution {
3. public:
4.     void preorder(TreeNode* root,vector<TreeNode*> &vec)
5.     {
6.         if(root)
7.         {
8.             vec.emplace_back(root);
9.             preorder(root->left,vec);
10.             preorder(root->right,vec);
11.         }
12.     }
13.     void flatten(TreeNode* root) {
14.         vector<TreeNode*> vec;
15.         preorder(root,vec);
16.         int n=vec.size();
17.         for(int i=1;i<n;i++)
18.         {
19.             TreeNode* prev=vec[i-1],*cur=vec[i];
20.             prev->left=nullptr;
21.             prev->right=cur;
22.         }
23.         
24.     }
25. };

复制代码

做法二：空间复杂度O(1)，对于一个节点，如果左子节点为空，则不必要操纵，如果不为空，那么对于右边，要找到左子树最右的节点，把右节点毗连上去，然后再把左子树连到右边即可。非常奇妙的做法

2. class Solution {
3. public:
4.     void flatten(TreeNode* root) {
5.         TreeNode* cur=root;
6.         while(cur!=nullptr)
7.         {
8.             if(cur->left!=nullptr)
9.             {
10.                 auto next=cur->left;
11.                 auto predecessor=next;
12.                 while(predecessor->right!=nullptr)predecessor=predecessor->right;
13.                 predecessor->right=cur->right;
14.                 cur->left=nullptr;
15.                 cur->right=next;
16.             }
17.             cur=cur->right;
18.         }
19.     }
20. };

复制代码

---

从前序与中序遍历序列构造二叉树
做法一：递归，前序遍历第一个节点是根节点，中序遍历则是[左子树，根节点，右子树]，我们可以先根据前序定位根节点，然后根据中序才能知道哪些在左边，哪些在右边。递归构建即可

2. class Solution {
3. public:
4.     unordered_map<int,int> mp;
5.     TreeNode* build(vector<int>& preorder,vector<int>& inorder,int pl,int pr,int il,int ir)
6.     {
7.         if(pl>pr)return nullptr;
8.         int p_root=pl;
9.         int in_root=mp[preorder[p_root]];
10.         TreeNode* root=new TreeNode(preorder[p_root]);
11.         int sz_l=in_root-il;
12.         root->left=build(preorder,inorder,pl+1,pl+sz_l,il,in_root-1);
13.         root->right=build(preorder,inorder,pl+sz_l+1,pr,in_root+1,ir);
14.         return root;
15.     }
16.     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
17.         int n=preorder.size();
18.         for(int i=0;i<n;i++)
19.         {
20.             mp[inorder[i]]=i;
21.         }
22.         return build(preorder,inorder,0,n-1,0,n-1);
23.     }
24. };

复制代码

做法二：迭代 先放养，因为肯定会忘记

---

路径总和III
做法一：直接遍历每个节点，对每个节点dfs看有几个满意的路径

2. class Solution {
3. public:
4.     int rootsum(TreeNode* root,long long target)
5.     {
6.         if(!root)return 0;
7.         int ans=0;
8.         if(root->val==target)ans++;
9.         ans+=rootsum(root->left,target-root->val);
10.         ans+=rootsum(root->right,target-root->val);
11.         return ans;
12.     }
13.     int pathSum(TreeNode* root, long long targetSum) {
14.         if(!root)return 0;
15.         int ans=rootsum(root,targetSum);
16.         ans+=pathSum(root->left,targetSum);
17.         ans+=pathSum(root->right,targetSum);
18.         return ans;
19.     }
20. };

复制代码

做法二：可以利用前缀和，用哈希表将对应前缀和和数量对应起来。如果遍历到某一前缀和，前缀和-target的数量就是现在路径的总和为target的线路。要记得遍历前哈希加1，递归后面要减去1

2. class Solution {
3. public:
4.     unordered_map<long long,int> pre;
5.     int dfs(TreeNode *root,long long cur,int target)
6.     {
7.         if(!root)return 0;
8.         int ans=0;
9.         cur+=root->val;
10.         if(pre.count(cur-target))
11.         {
12.             ans=pre[cur-target];//哈希表存储对应值有几个
13.         }
14.         pre[cur]++;
15.         ans+=dfs(root->left,cur,target);
16.         ans+=dfs(root->right,cur,target);
17.         pre[cur]--;//因为遍历完左右子树就不存在这个前缀和了
18.         return ans;
19.     }
20.     int pathSum(TreeNode* root, int targetSum) {
21.         pre[0]=1;
22.         return dfs(root,0,targetSum);
23.     }
24. };

复制代码

---

二叉树的最近公共祖先 想起数链剖分了
做法一：哈希表

2. class Solution {
3. public:
4.     unordered_map<int,TreeNode*>fa;
5.     unordered_map<int,bool>vis;
6.     void dfs(TreeNode* root)
7.     {
8.         if(root->left)
9.         {
10.             fa[root->left->val]=root;
11.             dfs(root->left);
12.         }
13.         if(root->right)
14.         {
15.             fa[root->right->val]=root;
16.             dfs(root->right);
17.         }
18.     }
19.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
20.         fa[root->val]=nullptr;
21.         dfs(root);
22.         while(p!=nullptr)
23.         {
24.             vis[p->val]=true;
25.             p=fa[p->val];
26.         }
27.         while(q!=nullptr)
28.         {
29.             if(vis[q->val])return q;
30.             q=fa[q->val];
31.         }
32.         return nullptr;
33.     }
34. };

复制代码

---

二叉树中的最大路径和
做法：由于不能向上面走，以是不是树形dp。只必要递归即可。对于空节点，那么就是贡献度为0，递归的时间，要比力，该节点加左子树和右子树的和是否大于maxum，返回的不是和而是节点值加上max(left,right)，因为每个节点至多只出现一次

2. class Solution {
3. public:
4.     int maxSum=INT_MIN;
5.     int maxsum(TreeNode* root)
6.     {
7.         if(!root)return 0;
8.         int sum=root->val;
9.         int leftsum=maxsum(root->left);
10.         int rightsum=maxsum(root->right);
11.         //maxSum=max(maxSum,leftsum);
12.         //maxSum=max(maxSum,rightsum);
13.         if(leftsum>0)sum+=leftsum;
14.         else leftsum=0;
15.         if(rightsum>0)sum+=rightsum;
16.         else rightsum=0;
17.         maxSum=max(maxSum,sum);
18.         return root->val+max(leftsum,rightsum);
19.     }
20.     int maxPathSum(TreeNode* root) {
21.         maxsum(root);
22.         return maxSum;
23.     }
24. };

复制代码

---

岛屿数量
做法一：深度优先遍历，搜寻到一个节点，我们可以dfs周边满意条件的节点，如许就能把一整个岛屿全部化为海水。dfs了几次就代表有几个岛屿

1. class Solution {
2. public:
3.     void dfs(vector<vector<char>>& grid,int r,int c)
4.     {
5.         int nr=grid.size();
6.         int nc=grid[0].size();
7.         grid[r][c]='0';
8.         if(r-1>=0&&grid[r-1][c]=='1')dfs(grid,r-1,c);
9.         if(r+1<nr&&grid[r+1][c]=='1')dfs(grid,r+1,c);
10.         if(c-1>=0&&grid[r][c-1]=='1')dfs(grid,r,c-1);
11.         if(c+1<nc&&grid[r][c+1]=='1')dfs(grid,r,c+1);
12.     }
13.     int numIslands(vector<vector<char>>& grid) {
14.         int nr=grid.size();
15.         if(!nr)return 0;
16.         int nc=grid[0].size();
17.         int num=0;
18.         for(int r=0;r<nr;r++)
19.             for(int c=0;c<nc;c++)
20.             {
21.                 if(grid[r][c]=='1')
22.                 {
23.                     num++;
24.                     dfs(grid,r,c);
25.                 }
26.             }
27.         return num;
28.     }
29. };

复制代码

做法二：BFS实在差不多，也是加入pair构成的队列
做法三：好像能用并查集吧 我不会

---

腐烂的橘子
做法：BFS

1. class Solution {
2. public:
3.     int cnt;
4.     int dis[10][10];
5.     int dir_x[4]={0,1,0,-1};
6.     int dir_y[4]={1,0,-1,0};
7.     int orangesRotting(vector<vector<int>>& grid) {
8.        queue<pair<int,int>>q;
9.        cnt=0;
10.        int n=grid.size();
11.        int m=grid[0].size();
12.        for(int i=0;i<n;i++)
13.         for(int j=0;j<m;j++)
14.         {
15.             if(grid[i][j]==2)
16.             {
17.                 q.push({i,j});
18.                 //dis[i][j]=0;
19.             }
20.             else if(grid[i][j]==1)
21.             {
22.                 cnt++;
23.             }
24.         }
25.         if(q.empty()&&cnt)return -1;
26.         int ans=0;
27.         while(!q.empty())
28.         {
29.            int t=q.size();
30.            for(int k=0;k<t;k++)
31.            {
32.             pair<int,int> p=q.front();
33.             q.pop();
34.             for(int i=0;i<4;i++)
35.             {
36.                 int x=p.first+dir_x[i];
37.                 int y=p.second+dir_y[i];
38.                 if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]==1)
39.                 {
40.                 grid[x][y]=2;
41.                 q.push({x,y});
42.                 cnt--;
43.                  }
44.             }
45.                
46.             
47.             }
48.             if(!q.empty())ans++;
49.         }
50.         if(cnt)return -1;
51.         return ans;
52.     }
53. };

复制代码

---

课程表
做法一：拓扑排序

1. class Solution {
2. public:
3.     int du[2010];
4.     unordered_map<int,vector<int>>mp;
5.     bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
6.         for(auto cur:prerequisites)
7.         {
8.             du[cur[1]]++;
9.             mp[cur[0]].push_back(cur[1]);
10.         }
11.         queue<int> q;
12.         for(int i=0;i<numCourses;i++)
13.         {
14.             if(du[i]==0)q.push(i);
15.         }
16.         while(!q.empty())
17.         {
18.             int u=q.front();
19.             q.pop();
20.             numCourses--;
21.             for(auto num:mp[u])
22.             {
23.                 du[num]--;
24.                 if(du[num]==0)q.push(num);
25.             }
26.         }
27.         if(numCourses==0)return true;
28.         return false;
29.     }
30. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。