Cracking-- 4.7 在一颗二叉树中找两个节点的第一个共同祖先

分别记录从 root 到 node1 的path 到 node2的path，再找其中共同的部分

struct Node{
    int val;
    struct Node *left;
    struct Node *right;
    Node(int _val)
    {
        val = _val;
        left = NULL;
        right = NULL;
    }
};


bool getABPath(Node* root,vector<Node*> ansPiece, vector<Node*>& ansPiece1, vector<Node*>& ansPiece2, Node *a, Node *b)
{
    if(root == NULL)
        return false;
    if(root == a)
    {
        ansPiece1 = ansPiece;
        ansPiece1.push_back(root);
    }
    if(root == b)
    {
        ansPiece2 = ansPiece;
        ansPiece2.push_back(root);
    }
    if(ansPiece1.empty() == false && ansPiece2.empty() == false)
    {
        return true;
    }
    
    ansPiece.push_back(root);
    bool ret1 = false, ret2 = false;
    ret1 = getABPath(root->left,ansPiece,ansPiece1,ansPiece2,a,b);

    if(!ret1)
        ret2 = getABPath(root->right,ansPiece,ansPiece1,ansPiece2,a,b);
    if(ret2)
        return true;
    ansPiece.pop_back();
    return false;
}

Node* getCommonParent(Node *root, Node *a, Node *b)
{
    if(root == NULL || a == NULL || b == NULL)
        return root;
    if(a == b)
        return a;

    vector<Node*> ansPiece1;
    vector<Node*> ansPiece2;
    vector<Node*> ansPiece;
    getABPath(root, ansPiece, ansPiece1, ansPiece2, a, b);

    // doesn't exist in the tree
    if(ansPiece1.size() == 0 || ansPiece2.size() == 0)
        return NULL;
    int i;
    for(i = 0; i < ansPiece1.size() && i < ansPiece2.size(); i++)
    {
        if(ansPiece1[i] != ansPiece2[i])
            break;
    }
    
    return ansPiece1[i - 1];
}