[알고리즘] Leetcode #543 이진 트리의 직경 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

문제 설명

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is thGiven 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.

 

입출력 예

Example 1:

Input: root = [1,2,3,4,5] Output: 3 Explanation: 3is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2] Output: 1

 

Constraints

• The number of nodes in the tree is in the range [1, 104].
• -100 <= Node.val <= 100

 

Code

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를 더한 수로 구성한다. 이때, 최장 길이를 저장하는 숫자형 변수 (불변) longest를 부모함수(diameterOfBinaryTree)의 변수로 선언하면 중첩된 dfs 함수에서 로컬 변수로 정의되기 때문에 재할당을 위해 클래스 변수로 선언한다. 

 

---

 

 

I'm a Senior Student in Data Science ! 

데이터 사이언스를 공부하고 있는 학부생의 TIL 블로그입니다. 게시글이 도움 되셨다면 구독과 좋아요 :)