现在的位置: 首页 > 综合 > 正文

求一个二叉树中任意两个节点间的最大距离,两个节点的距离的定义是这两个节点间边的个数,比如某个孩子节点和父节点间的距离是1,和相邻兄弟节点间的距离是2,

2014年09月05日 ⁄ 综合 ⁄ 共 6535字 ⁄ 字号 评论关闭

 题目:
求一个二叉树中任意两个节点间的最大距离,两个节点的距离的定义是这两个节点间边的个数,比如某个孩子节点和父节点间的距离是1,和相邻兄弟节点间的距离是2,

优化时间空间杂度。

 

思路一:

计算一个二叉树的最大距离有两个情况:
情况A: 路径经过左子树的最深节点,通过根节点,再到右子树的最深节点。
情况B: 路径不穿过根节点,而是左子树或右子树的最大距离路径,取其大者。
首先算出经过根节点的最大路径的距离,其实就是左右子树的深度和;然后分别算出左子树和右子树的最大距离,三者比较,最大值就是当前二叉树的最大距离了。

 

代码如下:

  1. /*----------------------------- 
  2. Copyright by yuucyf. 2011.09.02 
  3. ------------------------------*/  
  4. #include "stdafx.h"  
  5. #include <iostream>  
  6. #include <assert.h>  
  7. using namespace std;  
  8.   
  9. typedef struct tagSBTreeNode  
  10. {  
  11.     tagSBTreeNode *psLeft;  
  12.     tagSBTreeNode *psRight;  
  13.     int nValue;  
  14.   
  15.     int nMaxLeft;  
  16.     int nMaxRight;  
  17.   
  18.     tagSBTreeNode()  
  19.     {  
  20.         psLeft = psRight = NULL;  
  21.         nValue = 0;  
  22.         nMaxLeft = nMaxRight = 0;  
  23.     }  
  24. }S_TreeNode;  
  25.   
  26.   
  27. void AddTreeNode(S_TreeNode *&psTreeNode, int nValue)  
  28. {  
  29.     if (NULL == psTreeNode)  
  30.     {  
  31.         psTreeNode = new S_TreeNode;  
  32.         assert(NULL != psTreeNode);  
  33.         psTreeNode->nValue = nValue;  
  34.     }  
  35.     else if (psTreeNode->nValue < nValue)  
  36.     {  
  37.         AddTreeNode(psTreeNode->psRight, nValue);  
  38.     }  
  39.     else  
  40.         AddTreeNode(psTreeNode->psLeft, nValue);  
  41. }  
  42.   
  43. int MaxDepth(const S_TreeNode *psTreeNode)  
  44. {  
  45.     int nDepth = 0;  
  46.     if (NULL != psTreeNode)  
  47.     {  
  48.         int nLeftDepth = MaxDepth(psTreeNode->psLeft);  
  49.         int nRightDepth = MaxDepth(psTreeNode->psRight);  
  50.         nDepth = (nLeftDepth > nRightDepth) ? nLeftDepth : nRightDepth;  
  51.         nDepth++;  
  52.     }  
  53.   
  54.     return nDepth;  
  55. }  
  56.   
  57. int MaxDistance(const S_TreeNode *psRootNode)  
  58. {  
  59.     int nDistance = 0;  
  60.     if (NULL != psRootNode)  
  61.     {  
  62.         nDistance = MaxDepth(psRootNode->psLeft) + MaxDepth(psRootNode->psRight);  
  63.         int nLeftDistance = MaxDistance(psRootNode->psLeft);  
  64.         int nRightDistance= MaxDistance(psRootNode->psRight);  
  65.           
  66.         nDistance = (nLeftDistance > nDistance) ? nLeftDistance : nDistance;  
  67.         nDistance = (nRightDistance > nDistance) ? nRightDistance : nDistance;  
  68.     }  
  69.       
  70.     return nDistance;  
  71. }  
  72.   
  73.   
  74.   
  75.   
  76. int _tmain(int argc, _TCHAR* argv[])  
  77. {  
  78.     S_TreeNode *psRoot = NULL;  
  79.     AddTreeNode(psRoot, 9);  
  80.     AddTreeNode(psRoot, 6);  
  81.     AddTreeNode(psRoot, 4);  
  82.     AddTreeNode(psRoot, 8);  
  83.     AddTreeNode(psRoot, 7);  
  84.     AddTreeNode(psRoot, 15);  
  85.     AddTreeNode(psRoot, 13);  
  86.     AddTreeNode(psRoot, 16);  
  87.     AddTreeNode(psRoot, 18);  
  88.   
  89.     cout << "任意两个节点间的最大距离为:" << MaxDistance(psRoot) << endl;  
  90.   
  91.     return 0;  
  92. }  

 

思路二:

思路一不是效率最高的,因为在计算二叉树的深度的时候存在重复计算。但应该是可读性比较好的,同时也没有改变原有二叉树的结构和使用额外的全局变量。这里之间给出代码,因为代码的注释已经写的非常详细了。

 

代码如下:

  1. int g_nMaxLeft = 0;  
  2. void MaxDistance_2(S_TreeNode *psRoot)  
  3. {  
  4.     // 遍历到叶子节点,返回  
  5.     if (NULL == psRoot)  
  6.         return;  
  7.   
  8.     // 如果左子树为空,那么该节点的左边最长距离为0  
  9.     if (psRoot->psLeft == NULL)  
  10.     {  
  11.         psRoot->nMaxLeft = 0;  
  12.     }  
  13.   
  14.     // 如果右子树为空,那么该节点的右边最长距离为0  
  15.     if (psRoot->psRight == NULL)  
  16.     {  
  17.         psRoot -> nMaxRight = 0;  
  18.     }  
  19.   
  20.     // 如果左子树不为空,递归寻找左子树最长距离  
  21.     if (psRoot->psLeft != NULL)  
  22.     {  
  23.         MaxDistance_2(psRoot->psLeft);  
  24.     }  
  25.   
  26.     // 如果右子树不为空,递归寻找右子树最长距离  
  27.     if (psRoot->psRight != NULL)  
  28.     {  
  29.         MaxDistance_2(psRoot->psRight);  
  30.     }  
  31.   
  32.     // 计算左子树最长节点距离  
  33.     if (psRoot->psLeft != NULL)  
  34.     {  
  35.         int nTempMax = 0;  
  36.         if (psRoot->psLeft->nMaxLeft > psRoot->psLeft->nMaxRight)  
  37.         {  
  38.             nTempMax = psRoot->psLeft->nMaxLeft;  
  39.         }  
  40.         else  
  41.         {  
  42.             nTempMax = psRoot->psLeft->nMaxRight;  
  43.         }  
  44.         psRoot->nMaxLeft = nTempMax + 1;  
  45.     }  
  46.   
  47.     // 计算右子树最长节点距离  
  48.     if (psRoot->psRight != NULL)  
  49.     {  
  50.         int nTempMax = 0;  
  51.         if(psRoot->psRight->nMaxLeft > psRoot->psRight->nMaxRight)  
  52.         {  
  53.             nTempMax = psRoot->psRight->nMaxLeft;  
  54.         }  
  55.         else  
  56.         {  
  57.             nTempMax = psRoot->psRight->nMaxRight;  
  58.         }  
  59.         psRoot->nMaxRight = nTempMax + 1;  
  60.     }  
  61.   
  62.     // 更新最长距离  
  63.     if (psRoot->nMaxLeft + psRoot->nMaxRight > g_nMaxLeft)  
  64.     {  
  65.         g_nMaxLeft = psRoot->nMaxLeft + psRoot->nMaxRight;  
  66.     }  
  67. }  

 

抱歉!评论已关闭.