[題目分析]後序遍歷最後訪問根結點即在遞歸算法中根是壓在棧底的采用後序非遞歸算法棧中存放二叉樹結點的指針當訪問到某結點時棧中所有元素均為該結點的祖先本題要找p和q 的最近共同祖先結點r 不失一般性設p在q的左邊後序遍歷必然先遍歷到結點p棧中元素均為p的祖先將棧拷入另一輔助棧中再繼續遍歷到結點q時將棧中元素從棧頂開始逐個到輔助棧中去匹配第一個匹配（即相等）的元素就是結點p 和q的最近公共祖先
typedef struct
{BiTree t;int tag;//tag= 表示結點的左子女已被訪問tag=表示結點的右子女已被訪問
}stack;
stack s[]s[];//棧容量夠大
BiTree Ancestor(BiTree ROOTpqr)//求二叉樹上結點p和q的最近的共同祖先結點r
{top=; bt=ROOT;
while(bt!=null ||top>)
{while(bt!=null && bt!=p && bt!=q) //結點入棧
{s[++top]t=bt; s[top]tag=; bt=bt>lchild;} //沿左分枝向下
if(bt==p) //不失一般性假定p在q的左側遇結點p時棧中元素均為p的祖先結點
{for(i=;i<=top;i++) s[i]=s[i]; top=top; }//將棧s的元素轉入輔助棧s 保存
if(bt==q) //找到q 結點
for(i=top;i>;i)//將棧中元素的樹結點到s去匹配
{pp=s[i]t;
for (j=top;j>;j)
if(s[j]t==pp) {printf(p 和q的最近共同的祖先已找到)return (pp);}
｝
while(top!= && s[top]tag==) top; //退棧
if (top!=)｛s[top]tag=;bt=s[top]t>rchild;｝ //沿右分枝向下遍歷
}//結束while(bt!=null ||top>)
return(null);//ｑp無公共祖先
｝//結束Ancestor
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23728.html
