•
문제 설명 : 이진 트리 중 두 노드 사이의 가장 긴 거리를 구한다.
•
풀이 방법
◦
결국 두 노드 사이의 긴 거리라고 해도, 이진트리이기 때문에 특정 노드의 left/right 간선 길이의 합일 것이다.
◦
그래서, 각 노드의 [왼쪽 트리의 최대 depth + 오른쪽 트리의 최대 depth]를 구하고 그 중 최대 값을 반환하였다.
•
시간복잡도 : → 정확하게는 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
복사