leetcode<236. 二叉树的最近公共祖先>

bool getpath(TreeNode* root,TreeNode* x,stack<TreeNode*>& path)
    {
        if(root == nullptr) return false;           //走到空节点即找不到返回失败
        path.push(root);                            //走到新节点就先入栈
        if(root == x) return true;                  //找到目标节点返回成功
        if(getpath(root->left,x,path))              //判断往左找是否成功
        {
            return true;
        }
        if(getpath(root->right,x,path))             //判断往右找是否成功
        {
            return true;
        }
        path.pop();                                 //出栈
        return false;                               //都没有就返回失败
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> ppath,qpath;          //定义两个栈用于存储路径
        getpath(root,p,ppath);                 //求p的路径
        getpath(root,q,qpath);                 //求q的路径
        while(ppath.size()!= qpath.size())    
        {
            if(ppath.size()>qpath.size())      //把长的部分去掉使得两个栈一样长
            {
                ppath.pop();
            }
            else
            {
                qpath.pop();
            }
        }
        while(ppath.top()!=qpath.top())        //找第一个相同节点
        {
            ppath.pop();
            qpath.pop();
        }
        return ppath.top();
    }