Search

Diameter of Binary Tree

문제 설명 : 이진 트리 중 두 노드 사이의 가장 긴 거리를 구한다.
풀이 방법
결국 두 노드 사이의 긴 거리라고 해도, 이진트리이기 때문에 특정 노드의 left/right 간선 길이의 합일 것이다.
그래서, 각 노드의 [왼쪽 트리의 최대 depth + 오른쪽 트리의 최대 depth]를 구하고 그 중 최대 값을 반환하였다.
시간복잡도 : O(N)O(N)정확하게는 2N일 것이다. 탐색 후 거꾸로 올라오면서 연산하는 과정도 필요하기 때문이다.
성공 코드
# 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: self.result = 0 def search_tree(node): # Leef 노드일 경우 if not node.left and not node.right: return 1 # 왼쪽/오른쪽 자식 트리의 최대 depth를 구한다. left = search_tree(node.left) if node.left else 0 right = search_tree(node.right) if node.right else 0 # 왼쪽 + 오른쪽 트리의 최대 depth를 더하면 최대 지름이 된다. self.result = max(self.result, left + right) # 각 노드는 하위 트리 중 더 depth가 큰 값에 1을 더하여 반환한다. # 상위 노드로 가면 1개의 간선이 추가되기 때문 return max(left, right) + 1 if root: search_tree(root) return self.result
Python
복사