[코테] 리트코드 트리 543. Diameter of Binary Tree

543. Diameter of Binary Tree

문제 링크

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

문제 설명

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.

제한 사항

• The number of nodes in the tree is in the range [1, 10^4].
• -100 <= Node.val <= 100

입출력 예 #1

1. Input : root = [1,2,3,4,5]
2. Output : 3
3. Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

입출력 예 #2

1. Input : root = [1,2]
2. Output : 1

문제 풀이

리프 노드부터 루트노드까지 상태값을 0, 1, 2씩으로 업데이트한다.

그리고 가장 긴 경로는 왼쪽 노드와 오른쪽 노드의 상태값에 2를 더한값과 같다.

class Solution:
    longest: int = 0

    def diameterOfBinaryTree(self, root: Optional[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