[LEET CODE] 543. Diameter of Binary Tree

# Problem

Given the root of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them.     Constraints: The number of nodes in the tree is in the range [1, 104]. -100 <= Node.val <= 100

 

# My Answer

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def dfs(tree):
            l=0
            r=0
            l0=0
            r0 =0
            
            if tree.left:
                a = dfs(tree.left)
                l = 1+a[1] # 가장 깊은 노드
                l0 = a[0] # 왼쪽 트리의 최대값 저장
                
            if tree.right:
                b = dfs(tree.right)
                r = 1+b[1] # 가장 깊은 노드     
                r0 = b[0] # 오른쪽 트리의 최대값 저장
                
            m = max(l+r,l0,r0) # 현재 최대값, 왼쪽, 오른쪽 트리중 각각 최대값
            return (m,max(l,r))
        
        return dfs(root)[0]

 

# Solution 1 - 상태값 누적 트리 DFS

class Solution:
    longest: int = 0

    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

리프 노드까지 탐색한 다음 부모로 거슬러 올라가면서 각각의 거리를 계산, 상태값 업데이트 (누적)

존재하지 않는 노드에는 -1 부여

 

거리 = left + right + 2

상태값 = max(left, right) + 1

ex) 자식 노드가 하나도 없는 경우 left, right = -1 , 거리 =0 , 상태값 = 0

자식 노드가 모두 있는 경우 left,right = 0, 거리 = 2, 상태값 = 1

 

longest 변수는 재할당을 해야하기 때문에 클래스 변수로 선언 ( 숫자이기 때문에)