【剑指Offer面试编程题】题目1509：树中两个结点的最低公共祖先--九度OJ

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

输入：: 输入可能包含多个测试样例。

对于每个测试案例，输入的第一行为一个数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

【解题思路】首先是树的输入，这个利用中序遍历的特点递归输入就行。然后，我们需要判断给出的两个节点是否都在树中，不在直接输出非法信息。若都在树中则继续查找，这个时候我们需要递归查找，给定一个头节点和两个待查的节点值，首先判断如果节点值等于头结点的节点值，那么公共节点肯定就是头节点；否则，继续在头结点的左支和右支中间查找，若两个节点值分居左右支树中，那么公共节点肯定也就是头结点。否则我们可以通过左支或者右支返回的节点得到公共节点。

注意根节点需要通过传地址调用才能返回值，所以create参数是指针的指针。

AC code:

#include <cstdio>

#include <set>

using namespace std;

struct nod

{

  int val;

  nod *lc,*rc;

};

set<int> setin;

void create(nod **nd)

{

  int tt;

  scanf("%d",&tt);

  if(tt==0) {nd=NULL; return;}

  else

  {

    setin.insert(tt);

    nod *newnd=new nod();

    newnd->val=tt;

    *nd=newnd;

    create(&(newnd->lc));

    create(&(newnd->rc));

  }

}

nod * lca(nod *nd,const int &n,const int &m)

{

  if(!nd) return NULL;

  if(nd->val==n || nd->val==m) return nd;

  nod *lnd=lca(nd->lc,n,m);

  nod *rnd=lca(nd->rc,n,m);

  if(lnd && rnd) return nd;

  return lnd?lnd:rnd;

}

int main()

{

  int n;

  scanf("%d",&n);

  for(int i=0;i<n;++i)

  {

    nod *head=NULL;

    setin.clear();

    create(&head);

    int n,m;

    scanf("%d%d",&n,&m);

    if(setin.find(n)==setin.end()  || setin.find(m)==setin.end())

    {

      printf("My God\n");

      continue;

    }

    nod *re=lca(head,n,m);

    printf("%d\n",re->val);

  }

  return 0;

}

/**************************************************************

    Problem: 1509

    User: huo_yao

    Language: C++

    Result: Accepted

    Time:160 ms

    Memory:4988 kb

****************************************************************/

题目链接：http://ac.jobdu.com/problem.php?pid=1509

九度-剑指Offer习题全套答案下载：http://download.csdn.net/detail/huoyaotl123/8276299

巴特西

【剑指Offer面试编程题】题目1509：树中两个结点的最低公共祖先--九度OJ

最新文章

热门文章