转载请注明出处：http://blog.csdn.net/ns_code/article/details/28113959

    剑指offer上的最后一题了，一个递归函数调了一下午，才得到正确的结果。

题目描写叙述：

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

输入：

输入可能包括多个測试例子。
对于每一个測试案例，输入的第一行为一个数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

    首先假设是二叉排序树自然不用说了，推断的一句就是该节点的值是否位于输入的这两个节点之间，能够用前序遍历来做。

    假设是普通的树或者二叉树，解题思路是一样的，能够考虑前序遍历，得到两个路径，用链表或数组保存起来，然后找出两条路径的最后一个公共节点就可以。也能够后序遍历的方式，遍历到输入的节点时，将该节点及其后面遍历到的节点都保存到一个链表或数组中，然后找出两条路径的第一个公共机节点就可以。

    以下採用的是前序遍历，并用数组保存路径的代码。

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef struct BTNode
{
	struct BTNode *lchild;
	struct BTNode *rchild;
	int data;
}BTNode,*BTree;

/*
前序遍历找出根节点到数据域为val的节点路径，保存在path数组中,
这里index是保存到path数组中的元素的下标，*len用来保存路径长度，
假设能找到val，则返回ture，找不到则返回false
*/
bool GetPreTraversePath(BTree pTree,int val,int *path,int index,int *len)
{
	if(pTree == NULL)
	{
		*len = 0;
		return false;
	}

	path[index] = pTree->data;
	if(pTree->data =http://www.mamicode.com/= val)>
/**************************************************************
    Problem: 1509
    User: mmc_maodun
    Language: C
    Result: Accepted
    Time:130 ms
    Memory:920 kb
****************************************************************/
    PS：寻找路径的递归代码调了一个下午，总算搞定了，每次碰到关于树的问题，一般都是三种遍历方式的变种来实现，自然想到递推，有些写着非常easy，有些写着总非常纠结，尤其要返回bool变量的时候，还是太菜，回头要抽个时间把二叉树的递归实现的一些题目好好总结下。