二叉树的最近公共祖先

思路一（逆向树）：o1和o2找到各自的父节点，直到公共的父节点（利用层序遍历找个各个节点的父节点，并把当前和其父节点映射，从而遍历o1和o2的父节点）。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

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
        unordered_map<int,int> m;
        queue<TreeNode*> q;
        q.push(root);
        m[root->val] = -1;
        while(!m.count(o1) || !m.count(o2)){//加入o1和o2都包含即可
            TreeNode* tmp = q.front();
            q.pop();
            if(tmp->left){
                m[tmp->left->val] = tmp->val;
                q.push(tmp->left);
            }
            if(tmp->right){
                m[tmp->right->val] = tmp->val;
                q.push(tmp->right);
            }
        }
        unordered_set<int> p;
        while(m.count(o1)){
            p.insert(o1);//加入o1的所有父节点
            o1 = m[o1];
          
        }
        while(!p.count(o2))//o1和o2的公共祖先
            o2 = m[o2];
        return o2;
    }

};

思路二（树的先序遍历）：几种情况

	如果o1和o2在树的左右两边即当前的根即是公共节点
    如果o1和o2都在右树，返回右树遍历的最近的公共根（即公共节点）
    如果o1和o2都在左树，同上。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

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
        return fun(root,  o1,  o2)->val;
    }
    TreeNode* fun(TreeNode* root,int o1,int o2){
        if(!root || root->val == o1 || root->val == o2)
            return root;
        TreeNode* l = fun(root->left,o1,o2);
        TreeNode* r = fun(root->right,o1,o2);
        if(!l)return r;//两个都在右树，返回右树遍历的公共节点
        if(!r)return l;//同上
        return root;//最近的公共节点
    }
};