파이썬 알고리즘 인터뷰 - 이진 트리의 직경

문제

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

입력

TreeNode
[1,2,3,4,5]

출력

3

먼저 내 코드에서 테스트 해보려면 배열을 리스트로 만드는 과정이 필요했다.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def make_tree_by(lst, idx):
    parent = None
    if idx < len(lst):
        value = lst[idx]
        if value == None:
            return

        parent = TreeNode(value)
        parent.left = make_tree_by(lst, 2 * idx + 1)
        parent.right = make_tree_by(lst, 2 * idx + 2)

    return parent

이런 식으로 배열을 이진트리로 변환해 주었다.

그리고 나서 풀기 시작했지만 영 감을 못잡고 있었다. 그래서 책에있는 풀이과정을 이해하려고 했다.

# 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:TreeNode):
            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를 더한 값과 같다.

하나 중요한 점이 변수를 함수 내에서 선언해서 사용하지 않고 바깥 클래스 변수로 선언해서 번거롭게 self.logest로 사용 했는지 알고 가야한다.
중첩 함수는 부모 함수의 변수를 자유롭게 읽어들일 수 있다. 그러나 중첩함수에서 부모 함수의 변수를 재할당하게 되면 참조 ID 변경되며 별도의 로컬 변수로 선언된다. 위 풀이에서 self.longest를 사용한 이유는 재할당을 해야 하기 떄문이다. 따라서 부모 함수의 변수를 그대로 사용할 수 없고, 함수 바깥에서 클래스 변수로 선언 후 사용했다.

만약 longest의 값이 숫자나 문자가 아니라 리스트나 딕셔너리 같은 자료형이라면 append()등의 메소드를 이용해 재할당 없이 조작이 가능하다. 중첩 함수 내에서도 변수의 값을 조작할 수 있다.
숫자나 문자인 경우는 불변 객체이기 때문에 중첩 함수 내에서는 값을 변경할 수 없다. 이 때문에 클래스 변수를 사용했다.

머리속에 너무 안 그려져서 손으로 한땀한땀 그려봤다. 이제야 조금 이해가 되는것 같다.

https://leetcode.com/problems/diameter-of-binary-tree/

Diameter of Binary Tree - LeetCode