剑指 Offer 68 - II. 二叉树的最近公共祖先

剑指 Offer 68 - II. 二叉树的最近公共祖先

class Solution {
public:
    vector Path;
    void PreOrder(TreeNode* root, TreeNode* p){    //preOrder记录root到p的路径
        if(!root) return;
        if(root==p) {
            Path.emplace_back(p);
            return;
        }
        else{
            Path.emplace_back(root);
            PreOrder(root->left,p);
            PreOrder(root->right,p);
            Path.pop_back();
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector pPath,qPath;
        TreeNode*res;
        PreOrder(root,p);
        pPath=Path;
        Path.clear();           //清空Path队列
        PreOrder(root,q);
        qPath=Path;
        int cur=0;
        while(cur
            if(pPath[cur]==qPath[cur]){
                res=pPath[cur];                //res记录p q路径最后相同的结点
                ++cur;
            }
            else return res;     
        }
        return res;
    }
};