题目： 求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2， 优化时间空间杂度。 思路一： 计算一个二叉树的最大距离有两个情况: 情况a: 路径经过左子
题目：
求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，
优化时间空间杂度。
思路一：
计算一个二叉树的最大距离有两个情况:
情况a: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
情况b: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
首先算出经过根节点的最大路径的距离，其实就是左右子树的深度和；然后分别算出左子树和右子树的最大距离，三者比较，最大值就是当前二叉树的最大距离了。
代码如下：
[cpp] view plaincopyprint?
/*----------------------------- copyright by yuucyf. 2011.09.02 ------------------------------*/ #include stdafx.h #include #include using namespace std; typedef struct tagsbtreenode { tagsbtreenode *psleft; tagsbtreenode *psright; int nvalue; int nmaxleft; int nmaxright; tagsbtreenode() { psleft = psright = null; nvalue = 0; nmaxleft = nmaxright = 0; } }s_treenode; void addtreenode(s_treenode *&pstreenode, int nvalue) { if (null == pstreenode) { pstreenode = new s_treenode; assert(null != pstreenode); pstreenode->nvalue = nvalue; } else if (pstreenode->nvalue { addtreenode(pstreenode->psright, nvalue); } else addtreenode(pstreenode->psleft, nvalue); } int maxdepth(const s_treenode *pstreenode) { int ndepth = 0; if (null != pstreenode) { int nleftdepth = maxdepth(pstreenode->psleft); int nrightdepth = maxdepth(pstreenode->psright); ndepth = (nleftdepth > nrightdepth) ? nleftdepth : nrightdepth; ndepth++; } return ndepth; } int maxdistance(const s_treenode *psrootnode) { int ndistance = 0; if (null != psrootnode) { ndistance = maxdepth(psrootnode->psleft) + maxdepth(psrootnode->psright); int nleftdistance = maxdistance(psrootnode->psleft); int nrightdistance= maxdistance(psrootnode->psright); ndistance = (nleftdistance > ndistance) ? nleftdistance : ndistance; ndistance = (nrightdistance > ndistance) ? nrightdistance : ndistance; } return ndistance; } int _tmain(int argc, _tchar* argv[]) { s_treenode *psroot = null; addtreenode(psroot, 9); addtreenode(psroot, 6); addtreenode(psroot, 4); addtreenode(psroot, 8); addtreenode(psroot, 7); addtreenode(psroot, 15); addtreenode(psroot, 13); addtreenode(psroot, 16); addtreenode(psroot, 18); cout 任意两个节点间的最大距离为: return 0; } /*-----------------------------copyright by yuucyf. 2011.09.02------------------------------*/#include stdafx.h#include #include using namespace std;typedef struct tagsbtreenode{ tagsbtreenode *psleft; tagsbtreenode *psright; int nvalue; int nmaxleft; int nmaxright; tagsbtreenode() { psleft = psright = null; nvalue = 0; nmaxleft = nmaxright = 0; }}s_treenode;void addtreenode(s_treenode *&pstreenode, int nvalue){ if (null == pstreenode) { pstreenode = new s_treenode; assert(null != pstreenode); pstreenode->nvalue = nvalue; } else if (pstreenode->nvalue psright, nvalue); } else addtreenode(pstreenode->psleft, nvalue);}int maxdepth(const s_treenode *pstreenode){ int ndepth = 0; if (null != pstreenode) { int nleftdepth = maxdepth(pstreenode->psleft); int nrightdepth = maxdepth(pstreenode->psright); ndepth = (nleftdepth > nrightdepth) ? nleftdepth : nrightdepth; ndepth++; } return ndepth;}int maxdistance(const s_treenode *psrootnode){ int ndistance = 0; if (null != psrootnode) { ndistance = maxdepth(psrootnode->psleft) + maxdepth(psrootnode->psright); int nleftdistance = maxdistance(psrootnode->psleft); int nrightdistance= maxdistance(psrootnode->psright); ndistance = (nleftdistance > ndistance) ? nleftdistance : ndistance; ndistance = (nrightdistance > ndistance) ? nrightdistance : ndistance; } return ndistance;}int _tmain(int argc, _tchar* argv[]){ s_treenode *psroot = null; addtreenode(psroot, 9); addtreenode(psroot, 6); addtreenode(psroot, 4); addtreenode(psroot, 8); addtreenode(psroot, 7); addtreenode(psroot, 15); addtreenode(psroot, 13); addtreenode(psroot, 16); addtreenode(psroot, 18); cout
思路二：
思路一不是效率最高的，因为在计算二叉树的深度的时候存在重复计算。但应该是可读性比较好的，同时也没有改变原有二叉树的结构和使用额外的全局变量。这里之间给出代码，因为代码的注释已经写的非常详细了。
代码如下：
[cpp] view plaincopyprint?
int g_nmaxleft = 0; void maxdistance_2(s_treenode *psroot) { // 遍历到叶子节点，返回 if (null == psroot) return; // 如果左子树为空，那么该节点的左边最长距离为0 if (psroot->psleft == null) { psroot->nmaxleft = 0; } // 如果右子树为空，那么该节点的右边最长距离为0 if (psroot->psright == null) { psroot -> nmaxright = 0; } // 如果左子树不为空，递归寻找左子树最长距离 if (psroot->psleft != null) { maxdistance_2(psroot->psleft); } // 如果右子树不为空，递归寻找右子树最长距离 if (psroot->psright != null) { maxdistance_2(psroot->psright); } // 计算左子树最长节点距离 if (psroot->psleft != null) { int ntempmax = 0; if (psroot->psleft->nmaxleft > psroot->psleft->nmaxright) { ntempmax = psroot->psleft->nmaxleft; } else { ntempmax = psroot->psleft->nmaxright; } psroot->nmaxleft = ntempmax + 1; } // 计算右子树最长节点距离 if (psroot->psright != null) { int ntempmax = 0; if(psroot->psright->nmaxleft > psroot->psright->nmaxright) { ntempmax = psroot->psright->nmaxleft; } else { ntempmax = psroot->psright->nmaxright; } psroot->nmaxright = ntempmax + 1; } // 更新最长距离 if (psroot->nmaxleft + psroot->nmaxright > g_nmaxleft) { g_nmaxleft = psroot->nmaxleft + psroot->nmaxright; } } int g_nmaxleft = 0;void maxdistance_2(s_treenode *psroot){ // 遍历到叶子节点，返回 if (null == psroot) return; // 如果左子树为空，那么该节点的左边最长距离为0 if (psroot->psleft == null) { psroot->nmaxleft = 0; } // 如果右子树为空，那么该节点的右边最长距离为0 if (psroot->psright == null) { psroot -> nmaxright = 0; } // 如果左子树不为空，递归寻找左子树最长距离 if (psroot->psleft != null) { maxdistance_2(psroot->psleft); } // 如果右子树不为空，递归寻找右子树最长距离 if (psroot->psright != null) { maxdistance_2(psroot->psright); } // 计算左子树最长节点距离 if (psroot->psleft != null) { int ntempmax = 0; if (psroot->psleft->nmaxleft > psroot->psleft->nmaxright) { ntempmax = psroot->psleft->nmaxleft; } else { ntempmax = psroot->psleft->nmaxright; } psroot->nmaxleft = ntempmax + 1; } // 计算右子树最长节点距离 if (psroot->psright != null) { int ntempmax = 0; if(psroot->psright->nmaxleft > psroot->psright->nmaxright) { ntempmax = psroot->psright->nmaxleft; } else { ntempmax = psroot->psright->nmaxright; } psroot->nmaxright = ntempmax + 1; } // 更新最长距离 if (psroot->nmaxleft + psroot->nmaxright > g_nmaxleft) { g_nmaxleft = psroot->nmaxleft + psroot->nmaxright; }}