参考二叉树的最大距离
求二叉树的深度代码很简洁，如下：
int DepthOfBinaryTree(BinaryTreeNode*pNode){
if (pNode==NULL) {
return 0;
}
else { //递归
return DepthOfBinaryTree(pNode->m_pLeft) > DepthOfBinaryTree(pNode->m_pRight) ?
DepthOfBinaryTree(pNode->m_pLeft) + 1 : DepthOfBinaryTree(pNode->m_pRight) + 1;
}
我们要求的二叉树的最大距离，肯定是某个节点左子树的高度加上右子树的高度加2，所以求出每个节点左子树和右子树的高度，取左右子树高度之和加2的最大值即可，假设空节点的高度为-1
代码如下：
int HeightOfBinaryTree(BinaryTreeNode*pNode, int&nMaxDistance){
if (pNode == NULL)
return -1; //空节点的高度为-1
//递归
int nHeightOfLeftTree = HeightOfBinaryTree(pNode->m_pLeft, nMaxDistance) + 1; //左子树的的高度加1
int nHeightOfRightTree = HeightOfBinaryTree(pNode->m_pRight, nMaxDistance) + 1; //右子树的高度加1
int nDistance = nHeightOfLeftTree + nHeightOfRightTree; //距离等于左子树的高度加上右子树的高度+2
nMaxDistance = nMaxDistance > nDistance ? nMaxDistance : nDistance; //得到距离的最大值
return nHeightOfLeftTree > nHeightOfRightTree ? nHeightOfLeftTree : nHeightOfRightTree;
}
