[leetcode] 이진 트리의 직경

트리가 주어졌을 때, 트리 안의 가장 긴 path를 구하는 문제이다.

트리를 탐색하여 맨 아래 리프 노드까지 내려간 후, 각각의 부모 노드로 거슬러 올라가면서 상태값(트리의 리프 노드에서 현재 노드까지의 거리)을 업데이트 해가면 된다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def diameterOfBinaryTree(self, root):

		self.longest_path = 0
    
    	# 트리 탐색하면서 상태값 구함
        def dfs(node):            
            if not node: return -1
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            # 왼쪽 노드에서 리프 노드까지의 거리(상태값) 
            # + 오른쪽 노드에서 리프 노드까지의 거리(상태값) 
            # + 2(부모 노드로 가는 거리)
            self.longest_path = max(self.longest_path, left + right + 2)     

			# 상태값
            return max(left, right) + 1
            

        dfs(root)
        return self.longest_path

self.longest_path 중첩 함수에서 클래스 변수를 사용한 이유?
: 중첩 함수에서 부모 함수의 변수를 재할당하면 참조 ID가 변경되며 별도의 로컬 변수로 선언된다.
따라서 부모 함수의 변수를 그대로 사용할 수 없고, 함수 바깥에서 클래스 변수로 선언 후 사용해야 한다.
변수가 숫자나 문자일 경우 중첩 함수 내에서는 값을 변경할 수 없고 클래스 변수를 사용해야 한다.