学步园

/************************************************************************/
/* 13、设计一个算法，找出二叉树上任意两个结点的最近共同父结点。
		复杂度如果是O(n2)则不得分。                                                        */
/************************************************************************/
//间指offer有解，子节点拥有指向父节点的指针
//每个节点到根节点都是一个链表， 求两个节点到根节点的第一个公共节点, 略 

//子节点没有指向父亲节点的指针, 还上面的思路，不过用栈把路径记录下来了
//求A节点和B节点最近共同父节点
//栈中记录root到A的路径pathA， 记录root到B的路径pathB
//比较pathA和pathB长度差d，长路径先出d个节点，然后pathA，pathB同时出栈，找第一个相等的节点 

/*栈中元素复制到list中*/
void stackToList(stack<BinaryNode*> nodeStack, list<BinaryNode*>& path1)
{
	while(!nodeStack.empty())
	{
		path1.push_back(nodeStack.top());
		nodeStack.pop();
	}
}
//后续遍历获得路径
bool g_isFind = false;
void postOrderFindPath(BinaryNode* root, BinaryNode* lhs, list<BinaryNode*>& path)
{
	if(g_isFind == false && root)
	{
			path.push_front(root);
			postOrderFindPath(root->m_left, lhs, path);
			postOrderFindPath(root->m_right, lhs, path);
			if(root == lhs )
			{
				g_isFind = true;
				return;
			}
			if(g_isFind == false)
				path.pop_front();
	}
}




BinaryNode* findPublicNode(BinaryNode* root, BinaryNode* lhs, BinaryNode* rhs)
{
	if(!root)
		return NULL;
	//寻找lhs的路径和rhs的路径，分别存入path1Link， path2Link
	list<BinaryNode*> path1;
	list<BinaryNode*>path2;
	stack<BinaryNode*> nodeStack;
	int pathFlag = 0;

	//先序遍历，并检查节点是否要查找的节点 
	postOrderFindPath(root, lhs, path1);
	g_isFind = false;
	postOrderFindPath(root, rhs, path2);

	int d = path1.size() - path2.size();
	list<BinaryNode*>::iterator longIter;
	list<BinaryNode*>::iterator shortIter;
	if(d > 0)
	{
		longIter = path1.begin();
		shortIter = path2.begin();
	}
	else
	{
		//path2先走d步
		longIter = path2.begin();
		shortIter = path1.begin();
	}
	//longIter先走d步，然后比较相等
	for(int i = 0; i < d; ++i)
		longIter++;
	while(*longIter != *shortIter)
	{
		longIter++;
		shortIter++;
	}
	return * longIter;
}
void preOrder(BinaryNode* root)
{
	if(!root)
		return;
	stack<BinaryNode*> nodeStack;
	BinaryNode* pTemp = root;
	while(pTemp || !nodeStack.empty())
	{
		if(pTemp)
		{
			cout << pTemp->m_data << "\t";
			nodeStack.push(pTemp);
			pTemp = pTemp->m_left;
		}
		else
		{
			pTemp = nodeStack.top();
			nodeStack.pop();
			pTemp = pTemp->m_right;
		}
	}
	

}
void testofPublicNode()
{
	const int size = 10;
	int iArr[size];

	initArr(iArr, size);
	showArr(iArr, size);
	BinaryNode* root = buildBinaryTree(iArr, 0, size - 1);

	preOrder(root);
	
	cout << findPublicNode(root, (root->m_left)->m_left, (root->m_left)->m_right)->m_data << endl;

}