프로그래밍의 아름다움: 두 갈래 트리 중 노드의 최대 거리 구하기

3171 단어
이 문제를 보자마자 두 갈래 나무의 깊이를 구하는 것이 연상되었다(좌우 나무의 깊이를 각각 구한 다음에 합병(최대치를 취하고 1)하여 뿌리 노드의 깊이를 얻었다(사실은 분치사상이다)
코드는 다음과 같습니다.

   
   
   
   
int Depth(Node * p)
{
int l_d , r_d;

if (p == NULL)
{
return 0 ;
}
l_d
= Depth(p -> lChild);
r_d
= Depth(p -> rChild);

return Max(l_d , r_d) + 1 ;
}

 
현재 우리는 노드의 최대 거리를 요구한다. 우리는 같은 방법으로 생각할 수 있다. 하나의 노드 A에 대해 그 자수 중 노드의 최대 거리는 반드시 A 좌자수의 깊이+A 우자수의 깊이이다. 그러므로 우리는'분치'의 사상으로 귀속적으로 해답을 구하고 하나의 MaxLen으로 최대치를 유지한다.

   
   
   
   
int MaxLen = 0 ;

int FindMaxLen(Node * p)
{
int l_Len , r_Len;

if (p == NULL)
{
return 0 ;
}
l_Len
= FindMaxLen(p -> lChild);
r_Len
= FindMaxLen(p -> rChild);
MaxLen
= Max(l_Len + r_Len , MaxLen);

return Max(l_Len , r_Len) + 1 ;
}

개인적으로 책보다 훨씬 깔끔한 것 같아요 ~
 

좋은 웹페이지 즐겨찾기