[리트코드] 543. 이진 트리의 직경 (Python)

Diameter of Binary Tree - LeetCode

문제

이진트리의 지름 구하기

 

과정

• 가장 긴 path의 '길이'를 구하면 된다.
• 이 때, 노드 사이의 길이란 노드 사이의 edge의 개수이다. 
• 예를 들어 아래의 경우 path [4,2,1,3] 나 [5,2,1,3]가 가장 길기 때문에 3이 반환된다.

#Given a binary tree 
    1
   / \ 
  2   3 
 / \ 
4   5 
#Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3]. 
#Note: The length of path between two nodes is represented by the number of edges between them.

 

입력

[1,2,3,4,5]

출력

3

 

풀이

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return 0

            left = dfs(node.left)
            right = dfs(node.right)

            self.ans = max(self.ans, left+right+1)
            return max(left, right)+1

        self.ans = 1
        dfs(root)
        
        return self.ans-1

 

한 줄 씩 해석해보기

def dfs(node):
    if not node:
        return 0

• dfs함수를 만들고 node라는 변수를 널어준다.
• 만약 노드가 없다면 0을 return한다

    left = dfs(node.left)
    right = dfs(node.right)

• left에는 현재 노드의 왼쪽 right에는 현재 노드의 오른쪽을 넣어준다.
• 계속 재귀 호출을 통해 왼쪽, 오른쪽의 각 노드까지 DFS로 탐색

    self.ans = max(self.ans, left+right+1)
    return max(left, right)+1

• 마지막 노드에서 거슬러 올라간다.
• 최종결과가 될 가장 긴 경로를 self.ans에 넣어준다.
• 리프 노드에서 현재 노드까지의 거리를 return한다.
• ex) 자식 노드가 없는 경우 
  left, right 모두 0
  거리 0+0+1 = 1
  상태값 = 1
  자식 노드가 모두 존재하는 경우(자식 노드가 둘다 상태값이 0 일 때)
  거리 1+1+1 = 3
  상태값 = 2

self.ans = 1
dfs(root)

return self.ans-1

• 최소값이 1이기때문에 self.ans에 1을 넣은 상태로 시작한다.
• return할때는 -1을 해준상태로 반환한다.