求二叉树两个节点的最近祖先节点

最近在看一些面试题，又遇到这个题了。我有印象我看到过，不过对解题思路就模模糊糊了，只记得很坑。所以这次拿出来，重新梳理一下，以备录。这次是在CrackCode上面看到的，原题描述如下： Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree. 应该不需要翻译吧，关键在于避免使用额外的空间存储信息；而且该树不是BST。看来该题的限制条件比较多，先来看看没有限制的条件。

如果该树是BST，如何做？

BST指的是二叉搜索树，即左子树的都比根节点小，右子树都比根节点大。这样的话就比较好做了。如果两个节点都比A节点小，即他们俩都在A的左子树中，如果两个节点都比A节点大，即他们都在A的右子树中。如果一大一小，那么就bingo了，A节点就是我们需要的。代码简单展示如下：

struct Node
{
    int key;
    Node *lchild, *rchild, *parent;
};

Node* find_LCA_BST(Node *head, Node *q, Node *p)
{
    if(head == NULL || q == NULL || q == NULL) return NULL;
    int left,right;
    if(q->key >= p->key)
    {
        right = q->key;
        left = p->key;
    }else
    {
        right = p->key;
        left = q->key;
    }
    while(head)
    {
        if(right < head->key)
            head = head->lchild;
        else if(left > head->key)
            head = head->rchild;
        else
            return head;
    }
}

如果该树不是一个BST，但是可以用额外内存空间

思路也很简单。从第一个节点遍历父节点，每次得到一个存入一个map中，一直到整颗树的根节点；然后再从第二个节点往上找，每找到一个就在map中查找是否已经存在，如果存在，那么存在的节点就是我们需要的。代码也比较简单：

struct Node
{
    int key;
    Node *lchild, *rchild, *parent;
};

Node* find_LCA_with_other_memory(Node *p, Node *q)
{
    if(p == NULL || q == NULL) return NULL;
    map<Node* bool> m;
    while(p)
    {
        m[p] = true;
        p = p->parent;
    }
    while(q && !m[q])
    {
        q = q->parent;
    }
    return q;
}

如果该节点中不包含指向父节点的指针

如果是这样的话，就显得比较复杂了。既然结构中没有父节点的指针，我们就只能从上往下找。那也就没有什么太好的投机取巧的办法，只能判断根节点是不是LCA，再判断根节点的左节点是不是LCA，判断根节点的右节点是不是LCA，如此循环下去，知道找到我们的目标为止。现在问题的关键就在于我们如何判断两个节点是不是某一个指定节点的子节点呢？好像也只有硬上的办法。首先遍历树，找到两个节点的路径，然后问题就转化为寻找两个相交链表的第一个公共节点。可能文字表述有点吃力，看一下代码：

struct Node
{
    int key;
    Node *lchild, *rchild, *parent;
};

bool find_node_path(Node* head, Node* p, vector<Node*> &path)
{
    if(head == NULL) return false;
    if(p == head)
    {
        path.push_back(head);
        return true;
    }
    else if(find_node_path(head->lchild, p, path))
    {
        path.push_back(head->lchild);
        return true;
    }
    else if(find_node_path(head->rchild, p, path))
    {
        path.push_back(head->rchild);
        return true;
    }
    return false;
}
Node* find_LCA_without_parent(Node* head, Node* p, Node*q)
{
    vector<Node*> path1, path2;
    bool find = find_node_path(head, p, path1);
    find &= find_node_path(head, q, path2);
    if(!find) return NULL;

    Node* res = NULL;
    int minLength = path1.size() > path2.size()?path2.size():path1.size();

    //寻找两个相交链表的第一个公共节点
    for(int i = path1.size()-minLength, j = path2.size()-minLength;i<path1.size() && j<path2.size();i++,j++)
    {
        if(path1[i] == path2[j])
            res = path1[i];
    }
    return res;
}

今天就先更新到这里。这个题目的变化实在是太多了，我还得在网上找找其他更好的方法。有一些比较复杂，以后理解了再补上，留个坑