二叉树公共组先，剑指Offer

class Solution {
public:
    //先找到 路径，从根节点出发
    bool getPath(TreeNode* root,list<TreeNode*>& path,int value){
        path.push_back(root);
        bool found=false;;
        if(root->val==value){
            found=true;
            return true;
        } 
        if(root->left)
            found=getPath(root->left,path,value);
        if(root->right)
            found= found ||getPath(root->right,path,value);

        if(!found)
            path.pop_back();
        return found;
    }
    //两条路径的最后一个公共结点就是组先
    int commonNode(const list<TreeNode*>&path1,const list<TreeNode*>&path2){
        list<TreeNode*>::const_iterator iter1=path1.begin();
        list<TreeNode*>::const_iterator iter2=path2.begin();

        TreeNode* pLast=nullptr;
        while(iter1!=path1.end() && iter2!=path2.end()){
            if(*iter1==*iter2)
                pLast=(*iter1);

            ++iter1;
            ++iter2;
        }
        return pLast->val;
    }
    //二叉树公共组先
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {

        list<TreeNode*> path1;
        getPath(root,path1,o1);

        list<TreeNode*> path2;
        getPath(root,path2,o2);

        return commonNode(path1,path2);

    }
};