LeetCode - 543. Diameter of Binary Code

leetcode.com/problems/diameter-of-binary-tree/

Diameter of Binary Tree - LeetCode

 

 

처음에는 무조건 root 노드를 통과해야 가장 긴 diameter가 생성된다고 생각해서 

다음과 같이 코드를 짰었다

left depth와 right depth를 더해서 max diameter를 구하는 방식으로 했었는데 아무해도 다음과 같을때 에러가 나는 경우가 있었다. 

 

 

 

위와같은 트리가 있을 때 root를 통과하지 않는 녹색의 5와 7이 가장 긴 diameter를 가지고 있다.

 

따라서 다음과 같이 코드를 작성하게 되었고

 

 

기본적으로 dfs라는 함수는 depth를 리턴하는 함수로 재귀적으로 사용되어지고

output은 diameter로써 전역 변수로 선언하여 값을 계산하게 된다.

 

null일 경우에는 -1를 리턴하고

output 즉 diameter는 왼쪽의 depth와 우측의 depth를 더하고 null이 -1이기 떄문에 

상수 2를 더해주고 리턴해준다.