543. Diameter of Binary Tree (Tree, Depth-First Search, Binary Tree)

링크 - https://leetcode.com/problems/diameter-of-binary-tree/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

가장 긴 길을 찾기 위해서는 일단 임의의 두 노드들을 찍어보자. 거기서 더 긴 길을 찾으려면 각 노드의 child노드들을 찾아가야 한다. 따라서 가장 긴 길은 Leaf node 두 개를 연결하는 것이다. 

 

더 나아가 우리는 트리에서 각각의 노드들은 하나의 부모 노드와 최대 2개의 자식 노드들을 가지고 있다는 것을 알고 있다. 그래서 가장 긴 길은 한 노드를 중심으로 가장 긴 왼쪽 브랜치와 가장 긴 오른쪽 브랜치를 가질 것이다. 따라서 우리가 풀 알고리즘은 한 노드를 중심으로 가장 긴 왼쪽, 오른쪽 브랜치 값의 최대값을 찾아야 한다. 가장 긴 왼쪽과 오른쪽 브랜치를 찾아야 하므로 DFS가 가장 적합하다. 왜냐하면 DFS를 사용해야 가장 깊은 leaf node를 찾아내기 때문이다.

 

우리는 두가지 케이스들을 생각해야 한다.

1. 노드를 중심으로 왼쪽과 오른쪽의 브랜치 길이가 제일 길 때

2. 노드가 왼쪽 또는 오른쪽 브랜치 길이에 포함되어 있을 때

 

따라서 우리는 알고리즘을 다음과 같이 짜야한다

1. DFS를 적용해서 recursively하게 왼쪽 노드와 오른쪽 노드를 시작으로 가장 긴 브랜치들을 찾아내야 한다.

2. diameter라는 global variable를 사용해 가장 긴 길 값을 추적하고, 매 노드마다 현재 노드의 왼쪽 브랜치와 오른쪽 브랜치값을 통해 업데이트한다.

3. 왼쪽과 오른쪽 노드에서 가장 긴 브랜치 값을 반환한다.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        diameter = 0

        def dfs(node):
            # Leaf node will have no child nodes, return 0
            if not node:
                return 0

            # When you use global variable in local method, 
            # should use nonlocal
            nonlocal diameter

            # Get left and right branch paths
            left_branch_path = dfs(node.left)
            right_branch_path = dfs(node.right)

            # In every nodes, update diameter to have maximum value
            diameter = max(diameter, left_branch_path + right_branch_path)

            # Return current maximum paths including node itself, so add 1
            return max(left_branch_path, right_branch_path) + 1

        dfs(root)
        return diameter

복잡도

N 노드들이 있다고 할때

Time Complexity: O(N). dfs 함수로 recursively하게 모든 노드를 돌기 때문이다.

Space Complexity: O(N). 내부적으로 dfs함수를 recursively하게 돌기 때문이다. 이는 트리 height와도 관련이 있다. Worst case에서는 O(N)이겠지만, 트리가 balanced하다면 O(logN)일 것이다.