题解 | #在二叉树中找到两个节点的最近公共祖先#
在二叉树中找到两个节点的最近公共祖先
http://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116
1 思路
- 基础 不是搜索树，是普通树
- 公共祖先 和 相交的链表差异，指针没有next,只有root
- 找到bfs (queue)优化的痕迹
更新 不是 dfs,二十bfs，活用队列存树结构，用KV之map存关系；
1.1 实现错误思路
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
// write code here
vector<int> o1V;
vector<int> o2V;
queue<TreeNode*> q;
//题目肯定又1个
q.push(root);
//std::find(v.begin(), v.end(), key) != v.end()
while(std::find(o1V.begin(), o1V.end(), o1) != o1V.end() &&
std::find(o2V.begin(), o2V.end(), o2) != o2V.end()){
TreeNode* top = q.front();
//我怎么知道是更新哪个链表拉？ 只有局部关系，所有map两边共享
q.pop();
}
1.2 容易出错的位置
1.3 数据结构容易出错的地方
map哪儿插入，哪儿读取（count） vector如何查找
2 code
非递归 bfs变形
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
#include <map>
class Solution {
public:
/**
*
* @param root TreeNode类
* @param o1 int整型
* @param o2 int整型
* @return int整型
*/
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
// write code here
// vector<int> o1V;
// vector<int> o2V;
//hashmap
map<int,int> parentMap;
queue<TreeNode*> q;
//题目肯定又1个
q.push(root);
//parentMap.put(root,-1);//确认没有负数吧 java style, 注意键值
parentMap[root->val]=-1;
//java style containKeys ,c++ count
while(parentMap.count(o1) ==0 || parentMap.count(o2) ==0 ) //true true ; false false
{
TreeNode * top = q.front(); q.pop();
if(top->left){
q.push(top->left);
parentMap[top->left->val]= top->val;
}
if(top->right){
q.push(top->right);
parentMap[top->right->val]=top->val;
}
}
//get o1的父亲链条
vector<int> vec4a;//ArrayList<int> list4node1;
int curr = o1;
do{
//vec4a.push_back(parentMap[curr]);
vec4a.push_back(curr);
curr = parentMap[curr];
//}while(parentMap[curr]!= -1);
}while(curr!=-1);
int index = o2;
while(std::find(vec4a.begin(), vec4a.end(), index) == vec4a.end() ){// //stl style
index = parentMap[index];//find parent ,until find first in vector;
}
return index;
}
};
//参考
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
#include <map>
class Solution {
public:
/**
*
* @param root TreeNode类
* @param o1 int整型
* @param o2 int整型
* @return int整型
*/
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
// write code here
// vector<int> o1V;
// vector<int> o2V;
//hashmap
map<int,int> parentMap;
queue<TreeNode*> q;
//题目肯定又1个
q.push(root);
//parentMap.put(root,-1);//确认没有负数吧 java style, 注意键值
parentMap[root->val]=-1;
//stl style
//std::find(v.begin(), v.end(), key) != v.end()
//java style containKeys ,c++ count
while(parentMap.count(o1) ==0 || parentMap.count(o2) ==0 ) //true true ; false false
{
TreeNode * top = q.front();
q.pop();
if(top->left){
q.push(top->left);
parentMap[top->left->val]= top->val;
}
if(top->right){
q.push(top->right);
parentMap[top->right->val]=top->val;
}
}
//get o1的父亲链条
//ArrayList<int> list4node1;
vector<int> vec4a;
int curr = o1;
do{
//vec4a.push_back(parentMap[curr]);
vec4a.push_back(curr);
curr = parentMap[curr];
//}while(parentMap[curr]!= -1);
}while(curr!=-1);
int index = o2;
while(std::find(vec4a.begin(), vec4a.end(), index) == vec4a.end() ){
index = parentMap[index];//find parent ,until find first in vector;
}
return index;
}
};
todo
3 数据结构使用对比
需求：根据键值key修改对应的实值value。
若键存在，则值加1；若键不存在，则创建该键，并将键对应的值赋为1。
1 Java HashMap修改实值
Java的HashMap使用put()方法插入键值对元素<key, value>时，若键key相同，则会使用新值value覆盖之前的数据。
实现代码：
先判断键是否存在：
①键存在：先使用get()方法获取原值，加1后使用put()方法插入键值对元素，会覆盖旧值；
②键不存在：使用put()方法插入键值对元素。
HashMap<Character, Integer> mp = new HashMap<>();
/* 判断键key是否存在 */
//键存在
if(mp.containsKey(key)){
mp.put(key, map.get(key) + 1);
//键不存在，直接插入键值对元素
}else{
mp.put(key, 1);
}
简化写法：JDK 1.8的getOrDefault()方法
mp.put(key, mp.getOrDefault(key, 0) + 1);
2 C++ map修改实值
C++的map使用insert()函数插入键值对元素<key, value>时，若键key相同，则键值对元素插入失败，即不会覆盖之前的数据。
实现代码：
先判断键是否存在：
①键存在：使用迭代器或重载运算符[]更新值；
②键不存在：使用insert()函数插入键值对元素（即对组）。
map<char, int> mp;
/* 判断键key是否存在 */
map<char, int>::iterator pos = mp.find(key);
//键存在，根据迭代器或重载运算符[]赋值
if(pos != mp.end()){
//方法1：使用迭代器更新值
//pos->second = mp[key] + 1;
//方法2：使用重载运算符[]更新值
mp[key] += 1;
//键不存在，使用insert()函数，直接插入键值对元素（对组）
}else{
mp.insert(make_pair(key, 1));
}
简化写法：直接使用重载运算符[]获取并修改值，键不存在时则默认创建<key, 0>。
mp[key] += 1;
测试代码：
template<typename T1, typename T2>
void printMap(const map<T1, T2>& mp) { //形参使用const，避免被修改
//形参使用const后，遍历时需使用只读迭代器const_iterator
//使用typename关键字，防止编译器报错：C2760（语法错误，意外标记“标识符”）
for (typename map<T1, T2>::const_iterator it = mp.begin(); it != mp.end(); it++) {
cout << "key = " << (*it).first << " , value = " << it->second << endl;
}
cout << endl;
}
int main() {
map<char, int> mp;
mp.insert(make_pair('b', 2));
printMap<char, int>(mp);
//key = b , value = 2
/* 判断键key是否存在 */
char key = 'a';
/*
map<char, int>::iterator pos = mp.find(key);
//键存在，根据迭代器或重载运算符[]赋值
if (pos != mp.end()) {
//方法1：使用迭代器更新值
pos->second = mp[key] + 1;
//方法2：使用重载运算符[]更新值
//mp[key] += 1;
//键不存在，使用insert()函数，直接插入键值对元素（对组）
}
else {
mp.insert(make_pair(key, 1));
}
*/
//方法3：直接使用重载运算符[]获取并更新值
mp[key] += 1;
printMap<char, int>(mp);
//key = a , value = 1
//key = b , value = 2
}
海康威视公司福利 1061人发布
查看25道真题和解析