PAT甲级-1143 Lowest Common Ancestor (30 分)-白红宇的个人博客

PAT甲级-1143 Lowest Common Ancestor (30 分)

发布日期：2022-02-10 08:11:03 浏览次数：36 分类：技术文章

本文共 821 字，大约阅读时间需要 2 分钟。

题目：

分析：第一次写的时候先建树，然后在树中向父母进行查找判断，很麻烦。看了题解之后发现可以利用二叉树的特性来解决。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         using namespace std;int n,m,k;int pre[10090];map
          
           visi;int main(){ cin>>m>>n; Node *root = NULL; for(int i = 0;i
           
            >pre[i]; visi[pre[i]] = 1; } while(m--) { int a,b; cin>>a>>b; if(visi[a] == 0 && visi[b] == 0) printf("ERROR: %d and %d are not found.\n",a,b); else if(visi[a] == 0) printf("ERROR: %d is not found.\n",a); else if(visi[b] == 0) printf("ERROR: %d is not found.\n",b); else{ int t; for(int j = 0;j
            
             =a && pre[j]<=b) || (pre[j]>=b && pre[j]<=a)) break; } if(t == a) printf("%d is an ancestor of %d.\n",a,b); else if(t == b) printf("%d is an ancestor of %d.\n",b,a); else printf("LCA of %d and %d is %d.\n",a,b,t); } } return 0;}

转载地址：https://blog.csdn.net/qq_43567222/article/details/114385404 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Git的详细使用（上传到github）

下一篇：【算法】并查集

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目：

分析：第一次写的时候先建树，然后在树中向父母进行查找判断，很麻烦。看了题解之后发现可以利用二叉树的特性来解决。

发表评论

最新留言

关于作者

推荐文章