LeetCode 543. Diameter of Binary Tree

파이썬 알고리즘 인터뷰 문제 43번(리트코드 543번) Diameter of Binary Tree
https://leetcode.com/problems/diameter-of-binary-tree/

나의 풀이

# 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:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def helper(root):
            left = (0, 0)
            right = (0, 0)
            if not root:
                return (0, 0)
            if root.left:
                left = helper(root.left)
            if root.right:
                right = helper(root.right)
            
            diameter = max(left[0], right[0], left[1] + right[1])
            depth = 1 + max(left[1], right[1])
            
            return (diameter, depth)

        return helper(root)[0]

다른 풀이

# 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:
    diameter = 0
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
		    # 여기에 diameter = 0 선언하면 오류 발생.
        def helper(root):
            if not root:
                return -1

            left = helper(root.left)
            right = helper(root.right)
            self.diameter = max(self.diameter, left + right + 2)

            return 1 + max(left, right)

        helper(root)

        return self.diameter

배운 점

• 자식 함수는 부모 함수의 변수를 읽을 수 있다.
• 부모 함수 diameterOfBinaryTree에 diameter=0 을 하여도 자식 함수 helper가 이를 읽을 수 있다.
• 하지만 immutable 변수인 diameter 의 값을 업데이트하면 id 가 재할당되며 별도의 지역 변수가 되어 에러가 발생한다.
• 이를 해결하기 위해

1. 다른 풀이처럼 클래스 변수로 선언하거나
2. 부모 함수 diameterOfBinaryTree에 muttable 변수 diameter=[0]로 선언하고 자식 함수에서는 이 리스트의 요소만 바꾸어 리스트의 id를 바꾸지 않는 방법이 있다.