今天上午看了一道题，求二叉树的两个节点的最近公共父节点 充分利用递归的特性，写的很好，当时就纠结于不知道如何用递归来存储访问正确的路径，看人家写的，smart

充分利用递归的特性，写的很好，当时就纠结于不知道如何用递归来写，看人家写的，smart

以下代码转自该网站：http://blog.csdn.net/hhygcy/article/details/4660362

#include <vector>
bool nodePath (bstNode* pRoot, int value, std::vector<bstNode*>& path)
{
	if (pRoot==NULL) return false;
	if (pRoot->data!=value)
	{
		if (nodePath(pRoot->pLeft,value,path))
		{
			path.push_back(pRoot);
			return true;
		}
		else
		{
			if (nodePath(pRoot->pRight,value,path))
			{
				path.push_back(pRoot);
				return true;
			}
			else
				return false;
		}
	}
	else
	{
		path.push_back(pRoot);
		return true;
	}
}
bstNode* findLCACase1(bstNode* pNode, int value1, int value2)
{
	std::vector<bstNode*> path1;
	std::vector<bstNode*> path2;
	bool find = false;
	find |= nodePath(pNode, value1, path1);
	find &= nodePath(pNode, value2, path2);
	bstNode* pReturn=NULL;
	if (find)
	{
		int minSize = path1.size()>path2.size()?path2.size():path1.size();
		int it1 = path1.size()-minSize;
		int it2 = path2.size()-minSize;
		for (;it1<path1.size(),it2<path2.size();it1++,it2++)
		{
			if (path1[it1]==path2[it2])
			{
				pReturn = path1[it1];
				break;
			}
		}
	}
	return pReturn;
}