问题描述

试编写算法，求二叉树T中结点a和b的最近共同祖先。

试编写算法，求二叉树T中结点a和b的最近共同祖先。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode lchild*rchild;
} BiTNode *BiTree;
可用栈类型Stack的相关定义：
typedef struct {
BiTNode *ptr; // 二叉树结点的指针类型
int tag; // 0..1
} SElemType; // 栈的元素类型
Status InitStack(Stack &S);
Status StackEmpty(Stack S);
int StackLength(SqStack S);
Status Push(Stack &S SElemType e);
Status Pop(Stack &S SElemType &e);
Status GetTop(Stack S SElemType &e);
*********/
BiTree CommAncestor(BiTree T TElemType a TElemType b)
/* 求二叉树T中结点a和b的最近共同祖先 */
{

}

解决方案

http://blog.csdn.net/xzz_hust/article/details/8847427

解决方案二：

 BTreeNode_t *GetLastCommonParent( BTreeNode_t *pRoot BTreeNode_t *pNode1 BTreeNode_t *pNode2){    if( pRoot == NULL ) //说明是空树，不用查找了，也就找不到对应节点，则返回NULL        return  NULL;    if( pRoot == pNode1 || pRoot == pNode2 )//说明在当前子树的根节点上找到两个节点之一        return pRoot;    BTreeNode_t   *pLeft = GetLastCommonParent( pRoot->m_pLeft pNode1 pNode2);  //左子树中的查找两个节点并返回查找结果    BTreeNode_t   *pRight = GetLastCommonParent( pRoot->m_pRight pNode1 pNode2);//右子树中查找两个节点并返回查找结果    if( pLeft == NULL )//如果在左子树中没有找到，则断定两个节点都在右子树中，可以返回右子树中查询结果；否则，需要结合左右子树查询结果共同断定        return pRight;    if ( pRight == NULL )//如果在右子树中没有找到，则断定两个节点都在左子树中，可以返回左子树中查询结果；否则，需要结合左右子树查询结果共同断定        return pLeft;    return pRoot;//如果在左右子树中都找两个节点之一，则pRoot就是最低公共祖先节点，返回即可。}

解决方案三：
非递归方式：

 BTreeNode_t *GetLastCommonParent（BTreeNode_t *pRoot  BTreeNode_t *pNode1 BTreeNode_t *pNode2){    if( pRoot == NULL || pNode1 == NULL || pNode2 == NULL)         return NULL;    vector < BTreeNode_t *>  vec1;//用来保存从根节点到指定节点的遍历路径，前序遍历    vector <BTreeNode_t *>   vec2;    stack <BTreeNode_t *>   st;    bool  findflag1 = false;    bool findflag2 = false;    BTreeNode_t *commonParent = NULL;    while( pRoot != NULL || !st.empty() ){        while( pRoot != NULL ){            if( findflag1 == false){//没有找出所有的节点：从根节点到指定节点，在遍历时继续入栈                vec1.push_back( pRoot);                if( pRoot == pNode1)//找到，则设置标志位                    findflag1 = true;            }            if( findflag2 == false ){                vec1.push_back( pRoot);                if( pRoot == pNode2 )                    findflag2 = true;            }            if( findflag1 == true && findflag2 == true)//如果都已找到，则退出                break;            st.push( pRoot);            pRoot = pRoot->m_pLeft;        }        while( !st.empty()){            pRoot = st.top();            st.pop();            pRoot = pRoot->right;            if( findflag1 == false )//没有找到全部路径节点时，就需要将错误路径节点退出                vec1.pop_back();            if( findflag2 == false )                vec2.pop_back();        }        if( findflag1 == true && findflag2 == true)//如果都已找到，则退出            break;    }     if( findflag1 == true && findflag2 == true){//在两个遍历路径上查找最后一个相同的节点，就是最低公共祖先节点（最近公共父节点）         vector< BTreeNode_t *> ::iterator iter1 = vec1.begin();         vector< BTreeNode_t *> ::iterator iter2 = vec2.begin();         while( iter1 != vec1.end() && iter2 != vec2.end() ){             if( *iter1 == *iter2)                 commonParent = *iter1;             else                 break;             ++iter1;             ++iter2;         }     }     vec1.clear();     vec2.clear();     st.clear();     return commonParent;}

解决方案四：
http://zhidao.baidu.com/link?url=XWB_Ohn5Rdem5d9LMzIBMEDJ12q6synTnkzam1RD63BeBVyWKZVZZgwrLNa6xyl-y5oBNSM2eQ89qhl0IS_GaOY0Elp9Vtm2ZWRGRWY6wAi

解决方案五：
http://gouwu.baidu.com/question/328583857270789805.html?entry=qb_browse_default