PAT甲级-1151 LCA in a Binary Tree (30 分)-白红宇的个人博客

PAT甲级-1151 LCA in a Binary Tree (30 分)

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

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

题目：

分析：一般二叉树的LCA，先根据中序和前序建立二叉树，然后进行查找，根据高度来判断：

把高度低的其中一个节点向上移动到与另外一个高度相同为止

若移动到该节点时，刚好为另外一个节点，那么这个节点就是另外一个节点的ancestor

否则两个节点继续同时向上，直到找到相同的父母为止

#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;#define MAX 100001#define MM 1020typedef long long ll;int n,m,k;int in[10001];int pre[10001];struct Node{ int key; Node *left; Node* right; Node *last; int height;};Node *create(int prel,int prer,int inl,int inr,int h){ if(prel>prer) return NULL; Node *root = (Node*)malloc(sizeof(Node)); int key = pre[prel]; root->key = key; root->height = h; int idx = 0; for(int i = 0;i<=inr;i++) { if(in[i] == key) { idx = i; break; } } int num = idx - inl; root->left = create(prel+1, prel+num, inl,idx-1,h+1); if(root->left!=NULL) root->left->last = root; root->right = create(prel+num+1,prer, idx+1,inr,h+1); if(root->right!=NULL) root->right->last = root; return root;}Node* get(Node*root,int x){ if(root==NULL) return NULL; if(x == root->key) return root; Node *a = get(root->left,x); if(a!=NULL) return a; a = get(root->right,x); if(a!=NULL) return a;}void mov(Node *root,int a,int b){ Node*x = get(root,a); Node*y = get(root,b); if(x == NULL && y == NULL) printf("ERROR: %d and %d are not found.\n",a,b); else if(x == NULL) printf("ERROR: %d is not found.\n",a); else if(y == NULL) printf("ERROR: %d is not found.\n",b); else{ while(x->height != y->height) { if(x->height>y->height) x = x->last; else y = y->last; } if(x == y) { if(x->key == a) printf("%d is an ancestor of %d.\n",a,b); else printf("%d is an ancestor of %d.\n",b,a); } else{ while(x!=y) { x = x->last; y = y->last; } printf("LCA of %d and %d is %d.\n",a,b,x->key); } }}int main(){ cin>>m>>n; for(int i = 0;i
              
               >in[i]; for(int i = 0;i
               
                >pre[i]; Node *root=NULL; root=create(0,n-1,0,n-1,0); while(m--) { int a,b; cin>>a>>b; mov(root,a,b); } return 0;}

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

上一篇：AtCoder - arc006_3

下一篇：CodeForces-Magic Numbers

发表评论

关于作者

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

-- 愿君每日到此一游！

题目：

分析：一般二叉树的LCA，先根据中序和前序建立二叉树，然后进行查找，根据高度来判断：

发表评论

最新留言

关于作者

推荐文章