代码随想录算法训练营第36期DAY23

DAY23

530二叉搜索树的最小绝对差

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. private:
14.     vector<int> tv;
15.     void getv(TreeNode* root)
16.     {
17.         if(root==nullptr) return ;
18.         getv(root->left);
19.         tv.push_back(root->val);
20.         getv(root->right);
21.     }
22. public:
23.     int getMinimumDifference(TreeNode* root) {
24.     tv.clear();
25.     getv(root);
26.     if(tv.size()<2) return 0;
27.     int m=INT_MAX;
28.     for(int i=0;i<tv.size()-1;i++)
29.     {
30.         m=min(m,abs(tv[i]-tv[i+1]));
31.     }
32.     return m;
33.     }
34. };

递归法，待二刷：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. private:
14.     int result=INT_MAX;
15.     TreeNode* pre=nullptr;
16.     void getres(TreeNode* cur)
17.     {
18.         if(cur==nullptr) return ;
19.         getres(cur->left);
20.         //中：
21.         if(pre!=nullptr)
22.         {
23.             result=min(result,abs(cur->val-pre->val));
24.         }
25.         pre=cur;
26.         getres(cur->right);
27.     }
28. public:
29.     int getMinimumDifference(TreeNode* root) {
30.         getres(root);
31.         return result;
32.     }
33. };

501二叉搜索树中的众数

MAP：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. private:
14.     void gemap(TreeNode*cur,unordered_map<int,int> &map)
15.     {
16.         if(cur==nullptr) return;
17.         map[cur->val]++;
18.         gemap(cur->left,map);
19.         gemap(cur->right,map);
20.         return ;
21.     }
22.     //重载运算符：注意有很多细节,不要漏了static
23.     bool static mycmp(const pair<int,int>&a,const pair<int,int>&b)
24.     {
25.         return a.second>b.second;
26.     }
27. public:
28.     vector<int> findMode(TreeNode* root) {
29.         unordered_map<int,int>map;
30.         vector<int>result;
31.         if(root==nullptr) return result;
32.         gemap(root,map);
33.         vector<pair<int,int>> tmp(map.begin(),map.end());
34.         sort(tmp.begin(),tmp.end(),mycmp);
35.         result.push_back(tmp[0].first);
36.         for(int i=1;i<tmp.size();i++)
37.         {
38.             if(tmp[i].second==tmp[0].second) result.push_back(tmp[i].first);
39.             else break;
40.         }
41.         return result;
42.     }
43. };

递归带一点回溯：

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10.  * };
11.  */
12. class Solution {
13. private:
14.     int count=0;
15.     int maxcount=0;
16.     TreeNode* pre=nullptr;
17.     vector<int> result;
18.     void countnum(TreeNode* cur){
19.         if(cur==nullptr) return;
20.         countnum(cur->left);
21.         if(pre==nullptr)
22.         {
23.             count=1;
24.         }
25.         else if(cur->val==pre->val)
26.         {
27.             count++;
28.         }
29.         else{
30.             count=1
31.         }
32.         pre=cur;
33.         if(count==maxcount)
34.         {
35.             result.push_back(cur->val);
36.         }
37.         else if(count>maxcount)
38.         {
39.             result.clear();
40.             maxcount=count;
41.             result.push_back(cur->val);
42.         }
43.         countnum(cur->right);
44.         return ;
45.     }
46. public:
47.     vector<int> findMode(TreeNode* root) {
48.         //记得把private的变量重新赋值或者清空
49.         vector.clear();
50.         count=0;
51.         maxcount=0;
52.         pre=nullptr;
53.         countnum(root);
54.         return result;
55.     }
56. };

236二叉树的最近公共祖先

1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8.  * };
9.  */
10. class Solution {
11. public:
12.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
13.         //自己就是答案或者空树
14.         if(root==p||root==q||root==NULL)return root;
15.         TreeNode* l=lowestCommonAncestor(root->left,p,q);
16.         TreeNode* r=lowestCommonAncestor(roor->right,p,q);
17.         if(l!=NULL&&r!=NULL) return root;
18.         else if(l==NULL&&r!=NULL) return r;
19.         else if(l!=NULL&&r==NULL) return l;
20.         else return NULL;
21.     }
22. };