LeetCode > 543. Diameter of Binary Tree

문제 링크 : https://leetcode.com/problems/diameter-of-binary-tree/

최대 경로의 수를 구하는 문제인데 마지막 노드부터 거슬러 올라가며 구하는 문제인데 dfs와 이진탐색을 이용하여 구하는 문제이다.

아졸려ㅛ

# 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
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        
        
        def dfs(node):
            if node is None:
                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) 마지막 노드에서 거를러 올라감

2개의 값 계산,

거리(정답): 최종 결과가 될 가장 긴 경로 self.longest
left + right + 2
상태값: 리프 노드에서 현재 노드까지의 거리
max(left, right) + 1
[방법]

자식 노드가 하나도 없는 경우
left , right: 모두 -1
거리: 0 (left+right+2 = -1+-1+2)
상태값: 0 (max(left, right) + 1= -1+1=0)
자식 노드가 모두 존재하는 경우, (자식 노드가 둘 다 상태값이 0 일 때)
거리: 2 (left+right+2 = 0+0+2)
상태값: 1 (max(left, right) + 1= 0+1=1)

우선 제일 아래 노드부터 상태 값과 거리를 구하는데 상태값은 자식노드의 리프 노드로부터 현재 노드까지 길이, 거리는 왼쪽, 오른쪽 자식노드의 상태값에 2를 더한 수로 구성한다. 이때, 최장 길이를 저장하는 숫자형 변수 (불변) longest를 부모함수(diameterOfBinaryTree)의 변수로 선언하면 중첩된 dfs 함수에서 로컬 변수로 정의되기 때문에 재할당을 위해 클래스 변수로 선언한다.

상태값: 리프 노드에서 현재 노드까지의 거리
거리(정답): 왼쪽 자식 노드의 상태값과 오른쪽 자식 노드의 상태값의 합에 2를 더한 값(없는 경우 양쪽에 -1을 부여하기 때문에)

참고:
https://yerimoh.github.io/ALgo1001/
https://jiwon-lee-it.tistory.com/89