给定一个二叉树（不是二叉查找树），和两个节点，求这两个节点的最低公共父节点。
我们先介绍一个暴力的思路：
遍历并判断。首先我们写一个判断一个父节点是否含有一个子节点的函数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），有没有更好的方法呢？看下一篇文章
