[LeetCode][Python] 543. Diameter of Binary Tree

- 문제 링크: https://leetcode.com/problems/diameter-of-binary-tree/

- 난이도: Easy

 

binary tree의 지름을 구하는 문제

모든 노드에서 (왼쪽 subtree 높이 + 오른쪽 subtree 높이) 값들의 max를 구하면 된다. 지름이 꼭 root를 포함해야된다는 보장이 없어서 이렇게 한다.

 

dfs 함수는 node 부터 시작하는 subtree의 높이를 반환하도록 만든다

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        res = 0

        def dfs(node: Optional[TreeNode]):
            """
            :returns: height of current subtree
            """
            nonlocal res

            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)

            res = max(res, left + right)

            return 1 + max(left, right)

        dfs(root)
        return res