题目：

求树中两个结点的最低公共祖先

思路：

考虑一下几种情况：

1、该树为二叉搜索树

二叉搜索树是排序树，位于左子树点的结点都比父结点小，而位于右子树的结点都比父结点大，只需要从树的根结点开始和两个输入的结点进行比较。

如果当前结点的值比两个结点的值都大，那么最低的公共父结点一定在左子树，下一步就是遍历左子树；

如果当前结点的值比两个结点的值都小，那么最低的公共父结点一定在右子树；下一步就是遍历右子树；

如果当前结点的值介于两个结点的值之间，那么它就是两个结点的公共父结点，第一个找到的就是最低的公共父结点。

2、该树为二叉树，结点中有指向父结点的指针

有了父结点，就可以找到任意结点到根结点的路径；因此：

分别找到从两个结点开始到根结点的路径，即两个链表；

然后找到两个链表的第一个公共结点，就是最低的公共父结点；

3、该树为普通的树

从根结点开始，通过广度优先搜索，分别找到到达两个结点的路径；

然后找到两条路径的第一个公共结点，就是最低的公共父结点；

代码：

暂时先实现第三种条件

struct TreeNode{    int val;    vector
     
       children;};bool GetNodePath(TreeNode* pRoot,TreeNode* pNode,list
      
        &path){    if(pRoot==pNode)        return true;    path.push_back(pRoot);    vector
       
        ::iterator it=pRoot->children.begin();    bool found = false;    while(!found && it!=pRoot->children.end()){        found=GetNodePath(*it,pNode,path);        ++it;    }    if(!found)        path.pop_back();    return found;}TreeNode* GetLastCommonNode(const list
        
          &path1,const list
         
           &path2){    list
          
           ::const_iterator it1=path1.begin(); list
           
            ::const_iterator it2=path2.begin(); TreeNode* pLast=NULL; while(it1!=path1.end() && it2!=path2.end()){ if(*it1==*it2) pLast=*it1; it1++; it2++; } return pLast;}TreeNode* GetLastCommonParent(TreeNode* pRoot,TreeNode* pNode1,TreeNode* pNode2){ if(pRoot==NULL || pNode1==NULL || pNode2==NULL) return NULL; list
            
              path1; GetNodePath(pRoot,pNode1,path1); list
             
               path2; GetNodePath(pRoot,pNode2,path2); return GetLastCommonNode(path1,path2);}