[LC] 543. Diameter of Binary Tree

[seungriyou]

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

Approach

트리의 diameter란 다음과 같다.

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.

즉, 어떤 node를 지나는 longest path의 length는 다음과 같이 정의할 수 있다.

해당 node를 root로 하는 트리에 대해, left subtree와 right subtree의 max depth를 더한 값

중요한 것은, path가 root를 지나지 않을 수도 있기 때문에, 트리에 존재하는 모든 node에 대해서 위의 값을 구해보고, 최대값을 트래킹해야 한다는 점이다. (root를 지나지 않을 수도 있다는 말은 큰 힌트였다!)

따라서 구현의 용이함을 위해 max depth 알고리즘(#25)을 recursive 하게 구현하고, 최대값을 트래킹하는 코드(2번)를 추가한다.

diameter = 0

def max_depth(root):
    nonlocal diameter

    # base condition
    if not root:
        return 0

    # 1. left subtree와 right subtree의 max depth 구하기 (recur)
    left_max_depth, right_max_depth = max_depth(root.left), max_depth(root.right)

    # 2. 현재의 root 노드에 대해 diameter 업데이트 (**추가**)
    diameter = max(diameter, left_max_depth + right_max_depth)

    # 3. 현재 tree의 max depth 반환
    return max(left_max_depth, right_max_depth) + 1

Complexity

• Time: O(n) (모든 노드 방문)
• Space: O(height) (recursion stack) (balanced tree라면 height ~= logn, skewed tree라면 height ~= n)