[Tree] Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

 

트리를 순회하면서 최대 길이를 구하라는 문제이다.

예를들어 그림과 같은 트리가 있다면, 최대길이는 4->2->1->3 또는 5->2->1->3으로 3일 것이다.

 

1) 하나의 루트 노드를 기준으로 보면, left까지의 최대 길이에 1을 더한값과, right까지의 최대길이에 1을 더한값이 root의 최대 길이가 되며, 이것이 곧 트리 전체의 최대 길이가 될 것이다.

2) 루트가 아닌 노드 기준에서 보자면, 최대길이는 left와 right의 합이지만, 상위노드로 넘겨주어야 하는 값은 left와 right 중 더 큰 값 하나가 된다.

 

따라서 내 풀이에서는 '최대길이'와 '리턴값'을 별개로 관리한다.