LeetCode 543 solution

problem

Given the root of a binary tree, return the length of the diameter of the tree.

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.

The length of a path between two nodes is represented by the number of edges between them.

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

python

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter = 0
        def depth(node):
            if not node:
                return 0
            left_h = depth(node.left)
            right_h = depth(node.right)
            self.diameter = max(self.diameter,left_h + right_h)
            return 1 + max(left_h,right_h)
        depth(root)
        return self.diameter

DFS를 이용하면 쉽게 문제를 풀 수 있다. 해당 문제는 높이를 구하는 문제이기 때문에 각 노드를 방문할 때마다, 그 노드의 왼쪽과 오른쪽 자식의 높이를 계산하고, 이 높이들을 더해서 가장 큰 값을 찾아주면 된다. 이렇게 함으로써 우리는 전체 트리의 지름을 알 수 있다.

중요한 것은 트리의 모든 노드를 한 번씩만 확인해도 된다. 한 번씩만 확인하는 것이 가장 효율적인 계산법이 될 것이다. 높이를 계산하는 것도 중요하다. 왜냐하면 높이를 알아야 각 노드를 통과하는 경로의 길이를 알 수 있기 때문이다. 우리는 최대 값을 계속해서 갱신해나가면서 모든 노드에서 한 번씩만 계산하여 가장 긴 경로 diameter를 구해낼 수 있다.