题目:如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义”距离”为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离. 例如: 10 / \ 5 12 / \ 4 7 这棵树的话,最大距离为3.分别路径为4,5,10,12共3条边,7,5,10,12共3条边,所以最大距离为3.
递归的思想,分别考虑左右子树的,从根节点开始.
代码如下:
#include<iostream> using namespace std; struct BiTreeNode { int m_nValue; BiTreeNode *m_pleft; BiTreeNode *m_pright; int m_nMaxLeft; int m_nMaxRight; }; int nMaxLen = 0; void findMaxLen(BiTreeNode *pRoot); void addBiTreeNode(BiTreeNode *&pCurrent, int value); int main() { BiTreeNode *pRoot = NULL; addBiTreeNode(pRoot, 10); addBiTreeNode(pRoot, 5); addBiTreeNode(pRoot, 4); addBiTreeNode(pRoot, 7); addBiTreeNode(pRoot, 12); findMaxLen(pRoot); cout<<nMaxLen<<endl; return 0; } void findMaxLen(BiTreeNode *pRoot) { if(pRoot == NULL) return ; if(pRoot->m_pleft == NULL) pRoot->m_nMaxLeft = 0; if(pRoot->m_pright == NULL) pRoot->m_nMaxRight = 0; if(pRoot->m_pleft != NULL) findMaxLen(pRoot->m_pleft); if(pRoot->m_pright != NULL) findMaxLen(pRoot->m_pright); if(pRoot->m_pleft != NULL) { int nTempMax = 0; if(pRoot->m_pleft->m_nMaxLeft > pRoot->m_pleft->m_nMaxRight) nTempMax = pRoot->m_pleft->m_nMaxLeft; else nTempMax = pRoot->m_pleft->m_nMaxRight; pRoot->m_nMaxLeft = nTempMax + 1; } if(pRoot->m_pright != NULL) { int nTempMax = 0; if(pRoot->m_pright->m_nMaxLeft > pRoot->m_pright->m_nMaxRight) nTempMax = pRoot->m_pright->m_nMaxLeft; else nTempMax = pRoot->m_pright->m_nMaxRight; pRoot->m_nMaxRight = nTempMax + 1; } if(pRoot->m_nMaxLeft + pRoot->m_nMaxRight > nMaxLen) nMaxLen = pRoot->m_nMaxLeft + pRoot->m_nMaxRight; } void addBiTreeNode(BiTreeNode *&pCurrent, int value) { if(pCurrent == NULL) { BiTreeNode *pBiTree = new BiTreeNode(); pBiTree->m_nValue = value; pBiTree->m_pleft = NULL; pBiTree->m_pright = NULL; pCurrent = pBiTree; } else { if((pCurrent->m_nValue) > value) addBiTreeNode(pCurrent->m_pleft, value); else if((pCurrent->m_nValue) < value) addBiTreeNode(pCurrent->m_pright, value); } }
