题目1509：树中两个结点的最低公共祖先-九度

题目描述：

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

输入：

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

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

推荐指数：※※

来源：http://ac.jobdu.com/problem.php?pid=1509

这道题目是个树的遍历的题目。

在输入数据的时候使用递归方法。

注意，在路径记录的时候，要注意不管root->val是否等于val都要先记录路径，不然在根节点就是相同节点的时候就会出bug。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
using namespace std;
typedef struct Node{
	int val;
	Node *left;
	Node *right;
}Node;

Node *pre_build(){
	int val;
	scanf("%d",&val);
	if(val==0)
		return NULL;
	Node *node=new Node;
	node->val=val;
	node->left=pre_build();
	node->right=pre_build();
	return node;
}
int  find_path(int val,Node *root,vector<int> &p){
	if(root==NULL)
		return 0;
	p.push_back(root->val);
	if(root->val!=val){
		if(find_path(val,root->left,p)||find_path(val,root->right,p))
			return 1;
		else{
			p.pop_back();
			return 0;
		}
	}
	else
		return 1;
}
int main()
{
	int caseid,i;
	scanf("%d",&caseid);
	while(caseid--){
		Node *root=pre_build();
		int m1,m2;
		scanf("%d%d",&m1,&m2);
		vector<int> p1,p2;
		if(find_path(m1,root,p1)&&find_path(m2,root,p2)){
			for(i=0;i<p1.size()&&i<p2.size();i++){
				if(p1[i]!=p2[i])
					break;
			}
			printf("%d\n",p1[i-1]);
		}
		else
			printf("My God\n");
	}
	return 0;
}
           

后记：

到今天，才把《剑指offer》上的题目全部在oj上做完。虽然在途中掺杂了看了许多算法，不过一心做一件事的毅力还是不够，拖了1个多月。