문제43: 이진 트리의 직경

문제

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

입력


[1,2,3,4,5]

출력

풀이

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


class Solution(object):
  longest = 0
  def diameterOfBinaryTree(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    def dfs(node):
        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

문제43: 이진 트리의 직경

문제

입력

출력

풀이

새로운 개념