微软100题（75）二叉树最低公共父节点

二叉树两个结点的最低共同父结点（树）

题目：二叉树的结点定义如下：

struct TreeNode

{

int m_nvalue;

TreeNode* m_pLeft;

TreeNode* m_pRight;

};

输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。

分析：求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。

思路：可以找到从根节点到这两个结点的两条路径，这两条路径中最后一个相同的结点就是最低公共祖先

找路径：

bool findthepath(BinaryTreeNode* proot,BinaryTreeNode* pNode,vector<BinaryTreeNode*> &path)
{
 if(proot==NULL)
  return false;
 path.push_back(proot);
 if(proot==pNode)
  return true;
 bool found = findthepath(proot->m_left,pNode,path);
 if(!found)
  found = findthepath(proot->m_right,pNode,path);
 if(!found)
  path.pop_back();
}

找祖先

BinaryTreeNode* GetCommonParenent(BinaryTreeNode* proot,BinaryTreeNode* pnode1,BinaryTreeNode* pnode2)
{
 if(proot==NULL || pnode1==NULL || pnode2==NULL)
  return NULL;
 vector<BinaryTreeNode*> node1path,node2path;
 findthepath(proot,pnode1,node1path);
 findthepath(proot,pnode2,node2path);
 BinaryTreeNode* plastsame = proot;
 vector<BinaryTreeNode*>::iterator iter1 = node1path.begin();
 vector<BinaryTreeNode*>::iterator iter2 = node2path.begin();

 while (iter1!=node1path.end() && iter2!=node2path.end() && *iter1 == *iter2)
 {
  plastsame = *iter1;
  iter1++;
  iter2++;
 }
 return plastsame;
}