Day17 | Part7
约 47 个字 43 行代码 预计阅读时间 1 分钟
转为有序数组,然后求相邻的最小值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | void dfs(TreeNode* root, vector<int>& vec) {
if(!root) return;
dfs(root->left, vec);
vec.push_back(root->val);
dfs(root->right, vec);
}
int getMinimumDifference(TreeNode* root) {
vector<int> vec;
dfs(root, vec);
if(vec.size() <= 1) return 0;
int res = INT_MAX;
for(int i = 1; i < vec.size(); i ++)
res = min(res, vec[i] - vec[i - 1]);
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | void help(TreeNode* root, int& val, int& cnt, int& max_cnt, vector<int>& res) {
if(!root) return;
help(root->left, val, cnt, max_cnt, res);
cnt = root->val == val ? cnt + 1 : 1;
if(cnt == max_cnt) res.push_back(root->val);
else if (cnt > max_cnt) {
max_cnt = cnt;
res.clear(); // 清空res,之前的都失效了
res.push_back(root->val);
}
val = root->val;
help(root->right, val, cnt, max_cnt, res);
}
vector<int> findMode(TreeNode* root) {
int curr_val = 0, curr_cnt = 0, max_cnt = 0;
vector<int> res;
help(root, curr_val, curr_cnt, max_cnt, res);
return res;
}
|
| TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == q || root == p || !root) return root;
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right ,p , q);
if(left && right) return root;
else if(!left && right) return right;
else if(left && !right) return left;
else return nullptr;
}
|
