【IT筆試面試題整理】二叉樹任意兩個節點間最大距離

求一個二叉樹中任意兩個節點間的最大距離，兩個節點的距離的定義是這兩個節點間邊的個數，?比如某個孩子節點和父節點間的距離是1，和相鄰兄弟節點間的距離是2，優化時間空間復雜度。

一種是：經過根節點，此時只需要求出左右子樹的最大深度就可以

另一種：不經過根節點，此時需要遞歸求解左右子樹，然后比較左右子樹中最大距離，求大者

  1  #include "stdio.h"
  2  #include"stdlib.h" 
  3  struct NODE
  4     {
  5          NODE* pLeft;            // 左子樹
  6          NODE* pRight;          // 右子樹
  7          int nMaxLeft;          // 左子樹中的最長距離
  8          int nMaxRight;         // 右子樹中的最長距離
  9          int chValue;        // 該節點的值
 10     };
 11    
 12     int nMaxLen = 0;
 13    
 14     // 尋找樹中最長的兩段距離
 15     void FindMaxLen(NODE* pRoot)
 16     {
 17          // 遍歷到葉子節點，返回
 18          if(pRoot == NULL)
 19               return;
 20  
 21          // 如果左子樹為空，那么該節點的左邊最長距離為0
 22          if(pRoot -> pLeft == NULL)   
 23               pRoot -> nMaxLeft = 0;
 24          
 25    
 26          // 如果右子樹為空，那么該節點的右邊最長距離為0
 27          if(pRoot -> pRight == NULL)   
 28               pRoot -> nMaxRight = 0;
 29          
 30    
 31          // 如果左子樹不為空，遞歸尋找左子樹最長距離
 32          if(pRoot -> pLeft != NULL)       
 33               FindMaxLen(pRoot -> pLeft);
 34          
 35    
 36          // 如果右子樹不為空，遞歸尋找右子樹最長距離
 37          if(pRoot -> pRight != NULL)      
 38               FindMaxLen(pRoot -> pRight);
 39          
 40    
 41          // 計算左子樹最長節點距離
 42          if(pRoot -> pLeft != NULL)
 43          {
 44               int nTempMax = 0;
 45               if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)
 46               {
 47                    nTempMax = pRoot -> pLeft -> nMaxLeft;
 48               }
 49               else
 50               {
 51                    nTempMax = pRoot -> pLeft -> nMaxRight;
 52               }
 53               pRoot -> nMaxLeft = nTempMax + 1;
 54          }
 55    
 56          // 計算右子樹最長節點距離
 57          if(pRoot -> pRight != NULL)
 58          {
 59               int nTempMax = 0;
 60               if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)
 61               {
 62                    nTempMax = pRoot -> pRight -> nMaxLeft;
 63               }
 64               else
 65               {
 66                    nTempMax = pRoot -> pRight -> nMaxRight;
 67               }
 68               pRoot -> nMaxRight = nTempMax + 1;
 69          }
 70    
 71          // 更新最長距離
 72          if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)
 73          {
 74               nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
 75          }
 76      }
 77          
 78 NODE *createTree()
 79 {
 80     NODE *root;
 81     int data;
 82     printf("input data:");
 83     scanf("%d",&data);
 84     //printf("output data:%d\n",data);
 85     
 86     if(data==0)
 87       root=NULL;
 88     else/*根左右 前序建立二叉樹*/
 89     {
 90         root=(NODE*)malloc(sizeof(NODE));
 91         root->chValue=data;
 92         root->pLeft=createTree();
 93         root->pRight=createTree();    
 94     }
 95     return root;
 96 } 
 97 int main()
 98 {
 99     NODE  *root;
100     root=createTree();
101     FindMaxLen(root);
102     
103     printf("%d",nMaxLen);
104     return 0;
105 }

轉載于:https://www.cnblogs.com/WayneZeng/archive/2013/04/21/3034187.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/378572.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/378572.shtml
英文地址，請注明出處：http://en.pswp.cn/news/378572.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！