- 二叉树的最近公共祖先
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
TreeNode* ans;
bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) return false;
bool lson = dfs(root->left, p, q);
bool rson = dfs(root->right, p, q);
if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
ans = root;
}
return lson || rson || (root->val == p->val || root->val == q->val);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
dfs(root, p, q);
return ans;
}
};
|
- 二叉树展开为链表
- 将左子树插入到右子树的地方
- 将原来的右子树接到左子树的最右边节点
- 考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null
记得吧左子树置空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
void flatten(TreeNode* root) {
TreeNode* pre=root;
while(root!=nullptr){
pre=root->left;
if(root->left!=nullptr){
while(pre->right!=nullptr){
pre=pre->right;
}
pre->right=root->right;
root->right=root->left;
root->left=nullptr;
}
root=root->right;
}
}
};
|
- 二叉搜索树中的众数
第一种方法就是遍历一遍吧每个数出现的次数记录一下，然后换到vector来排序一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
private:
void searchBST(TreeNode* cur, unordered_map<int, int>& map) {
if (cur == NULL) return ;
map[cur->val]++;
searchBST(cur->left, map);
searchBST(cur->right, map);
return ;
}
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
}
public:
vector<int> findMode(TreeNode* root) {
unordered_map<int, int> map;
vector<int> result;
if (root == NULL) return result;
searchBST(root, map);
vector<pair<int, int>> vec(map.begin(), map.end());
sort(vec.begin(), vec.end(), cmp);
result.push_back(vec[0].first);
for (int i = 1; i < vec.size(); i++) {
if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
else break;
}
return result;
}
};
|
上面的代码可以优化，省掉闯创建vec和对vec排序的过程（上面这个主要是为了展示怎么对pair写排序），就是存储map的时候，同时记录最大值max，然后遍历map找到所有value为max的key就好了
再进一步优化空间就是采用递归充分利用二叉搜索树的性质，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public:
vector<int>res;
int imax = 0,count = 0;
TreeNode* pre;
void dfs(TreeNode* cur){
if(cur == NULL)return;
dfs(cur->left);
if(pre == NULL){
count = 1;
}
else if (pre->val == cur->val){
count++;
}
else{
count = 1;
}
if(count == imax)
res.push_back(cur->val);
if(count > imax){
res.clear();
res.push_back(cur->val);
imax = count;
}
pre = cur;
dfs(cur->right);
}
vector<int> findMode(TreeNode* root) {
if(root == NULL)return res;
dfs(root);
return res;
}
};
|
