面试题 04.08. 首个共同祖先

面试题 04.08. 首个共同祖先

共同祖先，选了常用的思路，也想不出来更好的思路。就是分别保存根节点到两个节点的路径，然后比较两条路径如果是重合的部分就一直往后面走，如果不是的话就是最后要寻找的节点。
需要注意的部分还是递归寻找到某个节点的路径这段代码，这个过程是在不断的尝试到达该节点的路径，所以如果在路径一颗子树里面没有找到，我们就要pop（）出去，继续尝试。

class Solution {
public:
       bool GetPath(TreeNode *node, TreeNode *target,vector &path) {
        if (node == nullptr)return false;
        path.push_back(node);
        if (node == target) {
          return true;
        }
        bool lf=false,rg=false;
        if(node->left)
        lf=GetPath(node->left, target,path);
        if(!lf&&node->right)
        rg=GetPath(node->right, target,path);
        if(!lf&&!rg)
        path.pop_back();
        return (lf||rg);
    }
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        TreeNode *ancestor;
        vector < TreeNode * > pathp;
        vector < TreeNode * > pathq;
        TreeNode *node = root;
         GetPath(node, p,pathp);
         GetPath(node, q,pathq);
        int psize = pathp.size();
        int qsize = pathq.size();
        for (int i = 0; i < psize && i < qsize; i++) {
            if (pathq[i] == pathp[i]) {
                ancestor = pathp[i];
            } else {
                break;
            }
        }
        return ancestor;
    }
};