題目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個多月。