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

算法分析

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

比如求节点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
    ****************************************************************/