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

1.将每个节点的父节点记录到字典kk中
2.找出o1和o2节点对应的指针
3.o1节点往上遍历到根节点，并将该路径所有节点的值存入集合path中
4.o2节点往上遍历到根节点，如果中途某个节点在path中，则直接返回该节点的值。

C++代码

void findkk(TreeNode* root, map<TreeNode*, TreeNode*>& kk) //记录每个节点的父节点，记录在字典kk中
{
    auto left = root->left;
    auto right = root->right;
    if(left != NULL)
    {
        kk[left] = root;
        findkk(left, kk);
    }
    if(right!=NULL)
    {
        kk[right] = root;
        findkk(right, kk);
    }
}

void findNode(TreeNode* root, int o1,int o2,vector<TreeNode*>& nodes)//找出这两个值对应节点的指针，nodes[0]是o1的节点指针，nodes[1]是o2的节点指针
{
    if(root == NULL)
        return;
    if(root->val==o1)
        nodes[0] = root;
    else if(root->val==o2)
        nodes[1] = root;
    findNode(root->left, o1,o2,nodes);
    findNode(root->right, o1,o2,nodes);
}


int lowestCommonAncestor(TreeNode* root, int o1, int o2) 
{
    map<TreeNode*, TreeNode*> kk;
    findkk(root, kk); //将每个节点的父节点存入字典kk
    vector<TreeNode*> nodes;
    nodes.resize(2, NULL);
    findNode(root, o1, o2, nodes);//找出值为o1和o2的节点，并将其指针存入nodes

    set<int> path; //将o1节点一直往上遍历，一直遍历的根节点，将这条路径上的节点指针存入集合path中
    auto p1 = nodes[0];
    while(p1 != root)
    {
        path.insert(p1->val);
        p1 = kk[p1];
    }
    path.insert(root->val);

    auto p2 = nodes[1]; //将o2节点一直往上遍历，每经过一个节点就判断这个节点是否在刚在o1节点经过的路径中，如果在就返回这个第一个公共节点的值
    while(p2!=root)
    {
        if(path.find(p2->val) != path.end())
        {
            return p2->val;
        }
        else{
            p2 = kk[p2];
        }
    }
    return root->val; //如果遍历到根节点，根节点一定是公共节点，返回该根节点的值
}