二叉树两个结点的最低公共祖先

问题：求一个普通二叉树中两个节点的公共祖先。

解决办法基于先序遍历，需要一个辅助栈存储两个节点的所有公共祖先。函数传入的两个节点参数为节点值，也可根据需要改为节点指针（需要预先判断是否为空），不影响整个过程。结果会包括以下特殊情况：

（1）给出的二叉树为空；

（2）给出的两个节点至少有一个不在二叉树中；

（3）其中一个节点为另一个节点的孩子节点，此时公共祖先为后者的父节点；

（4）两个节点中有一个为二叉树的根节点；

（5）两个节点相同。

下面是C++代码：

#include <iostream>
#include <stack>

using namespace std;

struct BinaryTreeNode
{
 int  m_nValue;
 BinaryTreeNode* m_pLeft;
 BinaryTreeNode* m_pRight;
};

stack<BinaryTreeNode*> L_list;//栈也可以放在CommonParents()中，并作为参数传给find(),这里偷懒了

void find(BinaryTreeNode* node,bool& flag_a,bool& flag_b,int a,int b)//递归
{
 if(node==NULL||(flag_a==true && flag_b==true))
  return;
 if(flag_a==false && node->m_nValue==a)
 {
  flag_a=true;
 }
 if(flag_b==false && node->m_nValue==b)
 {
  flag_b=true;
 }
        //只有两个都没找到的时候才压栈,此时两者的祖先已在栈中不必再入栈
 if(flag_a==false && flag_b==false)
  L_list.push(node);
 find(node->m_pLeft,flag_a,flag_b,a,b);
 find(node->m_pRight,flag_a,flag_b,a,b);
        //在没有全部找到的情况下，并且当前结点的子树已遍历完才弹出
 if((flag_a==false || flag_b==false) && L_list.size()>0 && node==L_list.top())
  L_list.pop();                                         
}

int CommonParents(BinaryTreeNode* head,int a,int b)
{
 if(head==NULL)
  return -1;
 bool flag_a=false;
 bool flag_b=false;
 int result;//这里需要假设节点值大于0，原因看下面
 
 find(head,flag_a,flag_b,a,b);

 if(L_list.size()==0)//为空说明没找到或有一个为根节点
 {
  if(flag_a==true && flag_b==true)//都找到说明有一个为根节点
   result=-2;
  else           //否则至少有一个不存在的点
   result=-1;
 }
 else
 {
  BinaryTreeNode* node=L_list.top();
  result=node->m_nValue;
 }

 return result;
}