[파이썬 알고리즘] 14장 - 이진 트리의 직경 (leetcode 543)⭐

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

Diameter of Binary Tree - LeetCode

 

<문제>

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

 

<예시>

          1
         / \
        2   3
       / \
      4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

 

---

 

참고한 코드

https://leetcode.com/problems/diameter-of-binary-tree/discuss/480877/543.-Diameter-of-Binary-Tree-and-124.-Binary-Tree-Maximum-Path-Sum

543. Diameter of Binary Tree and 124. Binary Tree Maximum Path Sum - LeetCode Discuss

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def height(root):
            nonlocal diameter
            if not root:
                return 0
            left = height(root.left)
            right = height(root.right)
            
            diameter = max(diameter, left+right)

            # max(left sub tree의 depth, right sub tree의 depth) + 1 (자식과 부모의 거리)
            return max(left, right)+1

        diameter = 0
        height(root)
        return diameter

코드 추천 ... ! 👍