已解決430363個問題，去搜搜看，總會有你想問的

以下問題是關于binarytreenode的一個問題，麻煩大佬幫忙看看~

首頁猿問以下問題是關于binarytree...

以下問題是關于binarytreenode的一個問題，麻煩大佬幫忙看看~

Java SQL Server

慕婉清6462132 2022-01-21 15:11:09

題目：給定節點類型為binarytreenode的三個指針p，q，rt,設rt為根節點，求距離p,q最近的這兩個節點的共同祖先節點。我的想法是先找到p 的所有祖先節點，存入棧中；同理找出q的，然后比較兩個棧中的節點，如果彈出的有不相等的，那么前一個就是所要求的。不知道代碼如何寫，大家幫幫忙！看來沒有人愿意幫忙??！

查看完整描述

1 回答

慕的地8271018

TA貢獻1796條經驗獲得超4個贊

struct
{ BiTree t;
int tag;//tag=0 表示結點的左子女已被訪問，tag=1表示結點的右子女已被訪問
}stack;

stack s[],s1[];

BiTree Ancestor(BiTree root,p,q)
{top=0; bt=root;
while(bt!=null ||top>0){
while(bt!=null && bt!=p && bt!=q){
s[++top].t=bt;
s[top].tag=0;
bt=bt->lchild;
} //沿左分枝向下

if(bt==p){
for(i=1;i<=top;i++)
s1[i]=s[i];
top1=top;
}//將棧s的元素轉入輔助棧s1 保存

if(bt==q) //找到q 結點。
for(i=top;i>0;i--){
pp=s[i].t;
for (j=top1;j>0;j--)
if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp);}
｝

while(top!=0 && s[top].tag==1) top--; //退棧

if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍歷

}//結束while(bt!=null ||top>0)

return(null);//q、p無公共祖先

｝//結束Ancestor

反對回復 2022-01-23

1 回答
0 關注
246 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

以下問題是關于binarytreenode的一個問題，麻煩大佬幫忙看看~

以下問題是關于binarytreenode的一個問題，麻煩大佬幫忙看看~

1 回答

添加回答

以下問題是關于binarytreenode的一個問題，麻煩大佬幫忙看看~

以下問題是關于binarytreenode的一個問題，麻煩大佬幫忙看看~