题解 | #在二叉树中找到两个节点的最近公共祖先#

在二叉树中找到两个节点的最近公共祖先

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();
            
            
        }

alt

1.2 容易出错的位置

alt

1.3 数据结构容易出错的地方

map哪儿插入，哪儿读取（count） vector如何查找

alt

2 code

非递归 bfs变形

c++
java
java
python


/**
 * 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
}