使用C语言求二叉树结点的最低公共祖先的方法

2020-01-26 14:59:17

字体：大中小

来源：转载

供稿：网友

算法分析

我们直接来分析O(n)的算法。

2015810120155494.jpg (344×246)

比如求节点F和节点H的最低公共祖先，先求出从根节点A到F的路径，再求出A到H的路径，那么最后一个相同的节点就是最低公共祖先。A->B->D->F和A->B->E->H，最后相同的节点事B，所以最低公共祖先是B节点。求根节点到指定节点的算法先前已经更新过了，复杂度是O(n)，所以总的时间复杂度是O(n)。
条件细化：
(1)树如果是二叉树，而且是二叉排序树。
             这中条件下可以使用二叉排序树的搜索功能找到最低公共祖先。
(2)树不是二叉排序树，连二叉树都不是，就是普通的树。
      1，如果树中有指向父节点的指针。
              这问题可以将问题转化为两个链表相交，求两个链表的第一个交点。
      2，如果树中没有指向父节点的指针。
              这问题就有点麻烦了。


具体来看获取从根节点到指定节点的函数代码：

struct BinaryNode{ char value; BinaryNode *left; BinaryNode *right;};

求跟节点到指定节点路径：

bool GetNodePath(BinaryNode *pRoot,BinaryNode *pNode,vector<BinaryNode*> &v){ if(pRoot==NULL)  return false; v.push_back(pRoot); if(pRoot==pNode)  return true; bool found=GetNodePath(pRoot->left,pNode,v); if(!found)  found=GetNodePath(pRoot->right,pNode,v); if(!found)  v.pop_back();}

求最低公共祖先节点：

BinaryNode* GetCommonParent(BinaryNode *pRoot,BinaryNode *pNode1,BinaryNode *pNode2){ if(pRoot==NULL || pNode1==NULL || pNode2==NULL)  return NULL; vector<BinaryNode*> v1,v2; GetNodePath(pRoot,pNode1,v1); GetNodePath(pRoot,pNode2,v2); BinaryNode *pLast=pRoot; vector<BinaryNode*>::iterator ite1=v1.begin(); vector<BinaryNode*>::iterator ite2=v2.begin(); while(ite1!=v1.end() && ite2!=v2.end()) {  if(*ite1==*ite2)   pLast=*ite1;  ite1++;  ite2++; } return pLast;}

来看一道具体的ACM题目

题目描述：
给定一棵树，同时给出树中的两个结点，求它们的最低公共祖先。

    输入：
    输入可能包含多个测试样例。
    对于每个测试案例，输入的第一行为一个数n(0<n<1000)，代表测试样例的个数。
    其中每个测试样例包括两行，第一行为一个二叉树的先序遍历序列，其中左右子树若为空则用0代替，其中二叉树的结点个数node_num<10000。
    第二行为树中的两个结点的值m1与m2(0<m1,m2<10000)。
    输出：
    对应每个测试案例，
    输出给定的树中两个结点的最低公共祖先结点的值，若两个给定结点无最低公共祖先，则输出“My God”。
    样例输入：
    2
    1 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 0
    6 8
    1 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 0
    6 12
    样例输出：
    2
    My God

思路
这道题我考虑的思路是

(1)后序遍历的思想,用栈保存到查找点的路径
(2)然后求两个栈第一个公共节点

AC代码

  #include <stdio.h>   #include <stdlib.h>       #define N 7000       typedef struct btree {     struct btree *lchild, *rchild;     int data;   } btree;       typedef struct stack {     int top;     btree* data[N];   } stack;       stack *first, *second;   int oneflag, secflag;       /**    * 根据前序序列递归构建二叉树    */   void createBtree(btree **t)   {     int data;     scanf("%d", &data);         if (data == 0) {       *t = NULL;     } else {       *t = (btree *)malloc(sizeof(btree));       (*t)->data = data;       createBtree(&(*t)->lchild);       createBtree(&(*t)->rchild);     }   }       /**    * 后序遍历二叉树,构造遍历栈    */   void postTraverse(btree *t, stack *s, int srcnum, int *flag)   {     if (t != NULL) {       btree *pre;       pre = NULL;           s->data[s->top ++] = t;       while (s->top > 0 || t) {         if (t) {           s->data[s->top ++] = t;           if (t->data == srcnum) {             *flag = 1;             break;           }           t = t->lchild;         } else {           t = s->data[-- s->top];           if (t->rchild == NULL || t->rchild == pre) {             pre = t;             t = NULL;           } else {             s->data[s->top ++] = t;             t = t->rchild;           }         }       }     }   }       /**    * 查找两个栈第一个公共元素    *    * T = O(n)    *    */   void stackCommonData(stack *f, stack *s)   {     int top, data, flag;         top = (f->top > s->top) ? s->top : f->top;         while (top > 0) {       if (f->data[top - 1]->data == s->data[top - 1]->data) {         data = f->data[top - 1]->data;         flag = 1;         break;       } else {         top --;       }     }         if (flag) {       printf("%d/n", data);     } else {       printf("My God/n");     }   }       /**    * 清理二叉树    *    */   void cleanBtree(btree *t)   {     if (t) {       cleanBtree(t->lchild);       cleanBtree(t->rchild);       free(t);     }   }           int main(void)   {     int n, sf, se;     btree *t;         scanf("%d", &n);     while (n --) {       createBtree(&t);       scanf("%d %d", &sf, &se);               first = (stack *)malloc(sizeof(stack));       first->top = 0;       oneflag = 0;       postTraverse(t, first, sf, &oneflag);           second = (stack *)malloc(sizeof(stack));       second->top = 0;       secflag = 0;       postTraverse(t, second, se, &secflag);           if (oneflag == 0 || secflag == 0 || first->top == 0 || second->top == 0) {         printf("My God/n");         cleanBtree(t);         continue;       } else {         stackCommonData(first, second);         cleanBtree(t);       }     }     return 0;   }

    /**************************************************************
        Problem: 1509
        User: wangzhengyi
        Language: C
        Result: Accepted
        Time:150 ms
        Memory:110212 kb
    ****************************************************************/

上一篇：最大子矩阵问题实例解析

下一篇：C语言中的链接编写教程