题目: 求一个二叉树中任意两个节点间的最大距离,两个节点的距离的定义是这两个节点间边的个数,比如某个孩子节点和父节点间的距离是1,和相邻兄弟节点间的距离是2, 优化时间空间杂度。 思路一: 计算一个二叉树的最大距离有两个情况: 情况A: 路径经过左子
题目:
求一个二叉树中任意两个节点间的最大距离,两个节点的距离的定义是这两个节点间边的个数,比如某个孩子节点和父节点间的距离是1,和相邻兄弟节点间的距离是2,
优化时间空间杂度。
思路一:
计算一个二叉树的最大距离有两个情况:
情况A: 路径经过左子树的最深节点,通过根节点,再到右子树的最深节点。
情况B: 路径不穿过根节点,而是左子树或右子树的最大距离路径,取其大者。
首先算出经过根节点的最大路径的距离,其实就是左右子树的深度和;然后分别算出左子树和右子树的最大距离,三者比较,最大值就是当前二叉树的最大距离了。
代码如下:
[cpp] view plaincopyprint?
/*----------------------------- Copyright by yuucyf. 2011.09.02 ------------------------------*/ #include "stdafx.h" #include <iostream> #include <assert.h> 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 <p><br> </p> <p> </p> <p><span>思路二:</span></p> <p>思路一不是效率最高的,因为在计算二叉树的深度的时候存在重复计算。但应该是可读性比较好的,同时也没有改变原有二叉树的结构和使用额外的全局变量。这里之间给出代码,因为代码的注释已经写的非常详细了。</p> <p> </p> <p><span>代码如下:</span></p> <p> </p> <p> </p> <p><strong>[cpp]</strong> view plaincopyprint?</p> <ol> <li><span><span>int</span><span> g_nMaxLeft = 0; </span></span></li> <li><span><span>void</span><span> MaxDistance_2(S_TreeNode *psRoot) </span></span></li> <li><span>{ </span></li> <li><span> <span>// 遍历到叶子节点,返回</span><span> </span></span></li> <li><span> <span>if</span><span> (NULL == psRoot) </span></span></li> <li><span> <span>return</span><span>; </span></span></li> <li><span> </span></li> <li><span> <span>// 如果左子树为空,那么该节点的左边最长距离为0</span><span> </span></span></li> <li><span> <span>if</span><span> (psRoot->psLeft == NULL) </span></span></li> <li><span> { </span></li> <li><span> psRoot->nMaxLeft = 0; </span></li> <li><span> } </span></li> <li><span> </span></li> <li><span> <span>// 如果右子树为空,那么该节点的右边最长距离为0</span><span> </span></span></li> <li><span> <span>if</span><span> (psRoot->psRight == NULL) </span></span></li> <li><span> { </span></li> <li><span> psRoot -> nMaxRight = 0; </span></li> <li><span> } </span></li> <li><span> </span></li> <li><span> <span>// 如果左子树不为空,递归寻找左子树最长距离</span><span> </span></span></li> <li><span> <span>if</span><span> (psRoot->psLeft != NULL) </span></span></li> <li><span> { </span></li> <li><span> MaxDistance_2(psRoot->psLeft); </span></li> <li><span> } </span></li> <li><span> </span></li> <li><span> <span>// 如果右子树不为空,递归寻找右子树最长距离</span><span> </span></span></li> <li><span> <span>if</span><span> (psRoot->psRight != NULL) </span></span></li> <li><span> { </span></li> <li><span> MaxDistance_2(psRoot->psRight); </span></li> <li><span> } </span></li> <li><span> </span></li> <li><span> <span>// 计算左子树最长节点距离</span><span> </span></span></li> <li><span> <span>if</span><span> (psRoot->psLeft != NULL) </span></span></li> <li><span> { </span></li> <li><span> <span>int</span><span> nTempMax = 0; </span></span></li> <li><span> <span>if</span><span> (psRoot->psLeft->nMaxLeft > psRoot->psLeft->nMaxRight) </span></span></li> <li><span> { </span></li> <li><span> nTempMax = psRoot->psLeft->nMaxLeft; </span></li> <li><span> } </span></li> <li><span> <span>else</span><span> </span></span></li> <li><span> { </span></li> <li><span> nTempMax = psRoot->psLeft->nMaxRight; </span></li> <li><span> } </span></li> <li><span> psRoot->nMaxLeft = nTempMax + 1; </span></li> <li><span> } </span></li> <li><span> </span></li> <li><span> <span>// 计算右子树最长节点距离</span><span> </span></span></li> <li><span> <span>if</span><span> (psRoot->psRight != NULL) </span></span></li> <li><span> { </span></li> <li><span> <span>int</span><span> nTempMax = 0; </span></span></li> <li><span> <span>if</span><span>(psRoot->psRight->nMaxLeft > psRoot->psRight->nMaxRight) </span></span></li> <li><span> { </span></li> <li><span> nTempMax = psRoot->psRight->nMaxLeft; </span></li> <li><span> } </span></li> <li><span> <span>else</span><span> </span></span></li> <li><span> { </span></li> <li><span> nTempMax = psRoot->psRight->nMaxRight; </span></li> <li><span> } </span></li> <li><span> psRoot->nMaxRight = nTempMax + 1; </span></li> <li><span> } </span></li> <li><span> </span></li> <li><span> <span>// 更新最长距离</span><span> </span></span></li> <li><span> <span>if</span><span> (psRoot->nMaxLeft + psRoot->nMaxRight > g_nMaxLeft) </span></span></li> <li><span> { </span></li> <li><span> g_nMaxLeft = psRoot->nMaxLeft + psRoot->nMaxRight; </span></li> <li><span> } </span></li> <li><span>} </span></li> </ol> <pre class="brush:php;toolbar:false">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; } }