1.1 二叉搜索树中的众数
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
1、结点左子树中所含结点的值小于等于当前结点的值
2、结点右子树中所含结点的值大于等于当前结点的值
3、左子树和右子树都是二叉搜索树
如果不是搜索二叉树，递归算法
std::vector<int> findMode(const alice::TreeNode *root){
std::vector<int> mode;
if(! root)
return mode;
auto inner = [](const auto& inner, const alice::TreeNode *root, std::unordered_map<int, int> &hash) -> void{
hash[root->data]++;
if(root->lchild)
inner(inner, root->lchild, hash);
if(root->rchild)
inner(inner, root->rchild, hash);
};
std::unordered_map<int, int> hash;
inner(inner, root, hash);
std::vector<std::pair<int, int>> data_hash(hash.begin(), hash.end());
auto cmp = [](const std::pair<int, int> &pair_1, const std::pair<int, int> &pair_2){
return pair_1.second > pair_2.second;
};
std::sort(data_hash.begin(), data_hash.end(), cmp);
mode.emplace_back(data_hash[0].first);
for(int i = 1; i < data_hash.size(); ++i)
if(data_hash[i].second == data_hash[0].second)
mode.emplace_back(data_hash[i].first);
return mode;
}
如果是二叉搜索树，递归算法
std::vector<int> findMode(const alice::TreeNode *root){
std::vector<int> mode;
if(! root)
return mode;
const alice::TreeNode *pre = nullptr;
int count = 0;
int max_count = 0;
auto inner = [&count, &max_count, &pre, &mode](const auto &inner, const alice::TreeNode *root) -> void{
if(root->lchild)
inner(inner, root->lchild);
if(! pre)
count = 1;
else if(pre->data == root->data)
++count;
else
count = 1;
pre = root;
if(count == max_count)
mode.emplace_back(root->data);
else if(count > max_count){
max_count = count;
mode.clear();
mode.emplace_back(root->data);
}
if(root->rchild)
inner(inner, root->rchild);
};
inner(inner, root);
return mode;
}
如果是二叉搜索树，非递归算法
std::vector<int> findMode(const alice::TreeNode *root){
std::vector<int> mode;
if(! root)
return mode;
std::stack<const alice::TreeNode *> stack;
const alice::TreeNode *cur_node = root;
const alice::TreeNode *pre = nullptr;
int count = 0;
int max_count = 0;
while(cur_node || ! stack.empty()){
if(cur_node){
stack.push(cur_node);
cur_node = cur_node->lchild;
}
else{
cur_node = stack.top();
stack.pop();
if(! pre)
count = 1;
else if(pre->data == cur_node->data)
++count;
else
count = 1;
if(count == max_count)
mode.emplace_back(cur_node->data);
else if(count > max_count){
max_count = count;
mode.clear();
mode.emplace_back(cur_node->data);
}
pre = cur_node;
cur_node = cur_node->rchild;
}
}
return mode;
}
1.2 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）
const alice::TreeNode *lowestCommonAncester(const alice::TreeNode *root, const alice::TreeNode *node_1, const alice::TreeNode *node_2){
if(! root || root == node_1 || root == node_2)
return root;
const alice::TreeNode *left = lowestCommonAncester(root->lchild, node_1, node_2);
const alice::TreeNode *right = lowestCommonAncester(root->rchild, node_1, node_2);
if(left && right)
return root;
else if(left)
return left;
else if(right)
return right;
else
return nullptr;
}
1.3 二叉搜索树的最近公共祖先
递归算法
const alice::TreeNode *comAncBTS(const alice::TreeNode *root, const alice::TreeNode *node_1, const alice::TreeNode *node_2){
if(! root)
return root;
if(node_1->data > root->data && node_2->data > root->data){
const alice::TreeNode *result = comAncBTS(root->rchild, node_1, node_2);
if(result)
return result;
}
if(node_1->data < root->data && node_2->data < root->data){
const alice::TreeNode *result = comAncBTS(root->lchild, node_1, node_2);
if(result)
return result;
}
return root;
}
非递归算法
const alice::TreeNode *comAncBTS(const alice::TreeNode *root, const alice::TreeNode *node_1, const alice::TreeNode *node_2){
if(! root)
return root;
const alice::TreeNode *cur_node = root;
while(cur_node){
if(cur_node->data > node_1->data && cur_node->data > node_2->data)
cur_node = cur_node->lchild;
else if(cur_node->data < node_1->data && cur_node->data < node_2->data)
cur_node = cur_node->rchild;
else
return cur_node;
}
return nullptr;
}