二叉树-最低公共父节点（1）

给定一个二叉树（不是二叉查找树），和两个节点，求这两个节点的最低公共父节点。
我们先介绍一个暴力的思路：
遍历并判断。首先我们写一个判断一个父节点是否含有一个子节点的函数hasnode(node* father,node* pnode) 然后我们从上到下遍历每一条路径；
有这么几种情况：

• 两节点在最低公共父节点的左子树
• 两节点在最低公共父节点的右子树
• 两节点在最低公共父节点的左边和右边各一个

头结点不需要判断，从头结点的left和right分别开始；

• 如果发现头结点的 左子树/右子树 两个节点都有，那么
  1，这个节点就是最低公共父节点，对应的情况是这个父节点等于其中的一个节点，那么就不需要往下找了
  2，否则递归调用这个函数，把当前节点设为头结点，递归查找
• 如果发现一个节点的左右两个分支分别含有两个节点，那么返回当前的头结点（注：我们这里使用递归调用，这个判断语句写在最后面的话，就不会把整个树的头结点当成符合条件的节点）

代码如下：

//find the last common parent node of two nodes
struct node
{
    int data;
    struct node* lnode;
    struct node* rnode;
};

//way1: check every path

bool hasnode(node* ptree, node* pnode)
{
    if (!ptree | !pnode)
        return;
    if (ptree == pnode)
        return true;
    else if (ptree->lnode)
        return hasnode(ptree->lnode, pnode);
    else if (ptree->rnode)
        return hasnode(ptree->rnode, pnode);
    else return false;
}
node* findLastCommonNode(node* ptree, node* node1, node* node2)
{
    if (!ptree || !node1 || !node2)
    {
        return 0;
    }
    bool leftHasNode1=0;
    bool leftHasNode2=0;

    if (ptree->lnode)
    {
        leftHasNode1 = hasnode(ptree->lnode, node1);
        leftHasNode2 = hasnode(ptree->lnode, node2);
    }
    if (leftHasNode1&&leftHasNode2)
    {
        if (ptree->lnode == node1 || ptree->rnode == node2)
            return ptree;
        else return findLastCommonNode(ptree->lnode, node1, node2);
        //像这种要一层一层的向下判断的，用递归可以减小代码的复杂度！
    }

    //check right
    bool rightHasNode1 = 0;
    bool rightHasNode2 = 0;
    if (ptree->rnode)
    {
        if (!leftHasNode1)//search only if left doesnot has node
        rightHasNode1 = hasnode(ptree->lnode, node1);
        if (!leftHasNode2)
        rightHasNode2 = hasnode(ptree->rnode, node2);
    }
    if (rightHasNode1&&rightHasNode2)
    {
        if (ptree->lnode == node1 || ptree->rnode == node2)
            return ptree;
        else return findLastCommonNode(ptree->rnode, node1, node2);
    }

    if (leftHasNode1&&rightHasNode2 || leftHasNode2&&rightHasNode1)
        return ptree;
}

这种思路由于要遍历整个树，因此复杂度为O(N2），有没有更好的方法呢？看下一篇文章