[DFS] Diameter of Binary Tree

처음에 입력값에 대한 문제 이해를 잘못 해서 한참을 헤맸다. 알고보니 링크드 리스트 형식으로 부모, 왼쪽 자식, 오른쪽 자식 형태의 노드가 입력이 되는거라고.. 저처럼 Array가 입력되는 걸로 이해해서 왼쪽 노드 = 부모노드*2, 오른쪽 노드 = 부모노드*2 + 1로 몇시간 삽질하지 마시길.. (없겠지만)

문제 접근하기

<문제>
Given the root of a binary tree, return 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.

The length of a path between two nodes is represented by the number of edges between them.
.
.
쉽게 말하면 노드와 노드 사이 가장 거리가 긴 경우를 찾으라는건데,
This path may or may not pass through the root.

이 파트가 상당히 중요한 힌트였던 거 같다.

난 처음에 가장 긴 diameter는 무조건 루트를 지날거라고 생각했는데, 생각해보니 이런 경우도 있다;

요점은, 각 노드를 root라고 봤을 때 그 노드를 기준으로 가장 긴 diameter를 찾아서 갱신하는 식으로 가야한다는 것이다.

즉, recursive하게 말단의 노드부터 현 노드 기점으로 가장 긴 경로를 계산해서 거슬러 올라가는 식으로 풀이가 진행될 것이다.

코드

class Solution:
	longest: int = 0
    
    def diameterOfBinaryTree(self, root):
    	def dfs(node):
        	if not node:
            	return -1
            left = dfs(node.left)
            right = dfs(node.right)
            self.longest = max(self.longest, left + right + 2)
            
            return max(left, right) + 1 
    
    dfs(root)
    return self.longest

처음엔 코드 보고 이게.. 뭔..??? 왜 2를 더하고 1을 더하고..? 했는데 차근차근 뜯어보니까

self.longest = max(self.longest, left + right + 2)

최종 리턴해야 하는 건 가장 긴 diameter라는 걸 잊지 말자. longest는 이 diameter를 뜻한다.

그러기 위해서 말단 노드에서부터 현 노드 기점으로 가장 긴 diameter가 뭔지 갱신하는 과정이다.
left + right + 2 는 현재 노드 기점 left node까지의 거리 + right node까지의 거리 + edge 2개를 의미한다.
dfs에서 return 하는 건 해당 노드까지의 최장 거리이다.

해당 노드까지의 최장 거리?

return max(left, right) + 1 

leaf 노드 기점으로 현재 노드까지의 거리를 말한다. 왼쪽, 오른쪽 중 더 긴 길이 + edge 1개다.

leaf 노드는 아마 0을 return 할 것이다. 노드가 없는 경우에는 -1을 return하기 때문에 max(-1, -1)+1이 되므로. 한번씩 그려보면서 과정을 따라가는 걸 추천한다!

참고

https://ihp001.tistory.com/102