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

层次遍历获取两个节点的公共父节点，先从根节点开始将o1与o2的上游节点全部加入到parent这个哈希表中，表的key为子节点的值，value为父节点的值，之后从parent中找到从根节点到o1的通路中所有的节点，将他们全部放到ancestor数组中，在ancestor中寻找o2的父节点，得到的第一个属于ancestor的节点即为公共父节点。

/**
 * 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
        queue<TreeNode*> q;
        unordered_map<int,int> parent;
        q.push(root);
        parent[root->val] = INT_MIN;
        while(!parent.count(o1) || !parent.count(o2))
        {   
            root = q.front();
            q.pop();
            if(root->left)
            {
                parent[root->left->val] = root->val;
                q.push(root->left);
            }
            if(root->right)
            {
                parent[root->right->val] = root->val;
                q.push(root->right);
            }
        }
        unordered_set<int> ancestor;
        while(parent.count(o1))
        {
            ancestor.insert(o1);
            o1 = parent[o1];
        }
        while(!ancestor.count(o2))
        {
            o2 = parent[o2];
        }
        return o2;
    }
};