常见面试算法题2：二叉树的最近公共父亲节点

程序员面试中对数据结构的考察，除了单链表，考察最为频繁的就是二叉树了，而二叉树的最近公共父节点又是较为常见的一道算法题，博主年前面试vivo互联网部门的时候就被考察过，下边介绍下这道算法题的思路和源码。
两个节点Node1和Node2的最近父节点可以用下边的思路得到：
首先，当Node1位于Node2的左子树或者右子树时，则Node1和Node2的最近父节点为Node2;
否则，反之当Node2位于Node1的左子树或者右子树时，则Node1和Node2的最近父节点为Node1;
再否则，Node1和Node2的最近父节点为以包含Node1和Node2l两个节点的最小子树的根节点。
经过上边的分析可以用递归的方法来解这道题，

BTNode *lowestCommonAncestor(BTNode *root, BTNode *p, BTNode *q)
{
   //发现目标节点则通过返回值标记该子树发现了某个目标结点 
    if(root == NULL || root == p || root == q)
    {
        return root;
    }
    //查看左子树中是否有目标结点，没有为NULL
    BTNode *left = lowestCommonAncestor(root->lchild, p, q);
    //查看右子树中是否有目标结点，没有为NULL
    BTNode *right = lowestCommonAncestor(root->rchild, p, q);

    if(left != NULL && right != NULL)
    {
        //都不为空，说明左右子树都有目标结点，则公共父节点就是本身 
        return root;
    }
    //如果发现了目标节点，则继续向上标记为该目标节点  
    return left == NULL ? right : left;
}