Home Diameter of Binary Tree
Post
Cancel

Diameter of Binary Tree

Leetcode Problem

Diameter of Binary Tree

주어진 Binary Tree에서 왼쪽 끝 노드부터 오른쪽 끝 노드까지의 최대 길이를 구하는 문제입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def __init__(self, maxi = 0):
        self.maxi = maxi

    def dfs(self, node):
        if not node:
            return 0
        nl = self.dfs(node.left)
        nr = self.dfs(node.right)
        self.maxi = max(self.maxi, nl + nr)
        return max(nl, nr) + 1
        
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.dfs(root)
        return self.maxi

solutions의 풀이를 정리했습니다.
instance variable을 활용하여 dfs 함수가 각 노드를 돌면서 왼쪽 최대 길이와 오른쪽 최대 길이의 합을 구하고, 최댓값을 구합니다.





참고

This post is licensed under CC BY 4.0 by the author.