[LeetCode] 543. Diameter of Binary Tree [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Diameter of Binary Tree - LeetCode>

1. 문제 (이진 트리의 직경)

이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라.

예를 들어, 위와 같은 트리는 4-2-1-3 or 5-2-1-3 으로 답은 3이다.

2. 풀이

DFS를 이용한 풀이

중첩 함수에서 숫자나 문자와 같은 불변 객체를 재할당하면 참조ID가 변경되므로 클래스 변수를 사용해야 한다!

3. 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    longest = 0 # 중첩함수에서 재할당하면 참조ID가 변경되므로 클래스 변수 이용
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def dfs(node: TreeNode) -> int:
            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

• 결과 :

방식	Status	Runtime	Memory	Language
DFS	[Accepted]	48 ms	16.4 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋