[原创]计算二叉树节点间最大距离

duweifu posted @ 2011年9月08日 15:59 in None with tags 二叉树 距离 非递归 , 1141 阅读
int MaxDistanceOfTree(TreeNodeEx *pRoot)
{
	if (pRoot == NULL)
	{
		return 0;
	}
	stack<TreeNodeEx*> nodeStack;
	TreeNodeEx *pNode = pRoot;
	int nMaxDist = 0;
	while (pNode != NULL || !nodeStack.empty())
	{
		if (pNode != NULL)
		{
			nodeStack.push(pNode);
			pNode = pNode->pLeft;
		} 
		else
		{
			pNode = nodeStack.top();
			nodeStack.pop();
			if (!pNode->visited)
			{
				pNode->visited = true;
				nodeStack.push(pNode);
				pNode = pNode->pRight;
			} 
			else
			{
				pNode->nLeft = (pNode->pLeft == NULL) ? 0 : max(pNode->pLeft->nLeft, pNode->pLeft->nRight) + 1;
				pNode->nRight = (pNode->pRight == NULL) ? 0 : max(pNode->pRight->nLeft, pNode->pRight->nRight) + 1;
				if (pNode->nLeft + pNode->nRight > nMaxDist)
				{
					nMaxDist = pNode->nLeft + pNode->nRight;
				}
				pNode = NULL;
			}
		}
	}

	return nMaxDist;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter