문제 설명
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].
문제 이해하기
트리의 직경을 구하는 문제인데, 직경이란 설명에도 나와있듯이 노드 간의 가장 긴 거리이다. 여기서 주의할 문장은 This path may or may not pass through the root.이다.
일종의 함정이라 할 수 있다.
왜냐하면 노드 간의 가장 긴 거리는 반드시 루트 노드를 거쳐야 하기 때문이다. 아마 루트 노드 1개만 입력으로 주어질 경우에는 pass through가 아니라서 저런 문장이 주어진게 아닌가 싶다.
전체 코드
# 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 __init__(self):
self.answer=0
def dfs(self,current)->int:
# if leaf node, then return
if current.left==None and current.right==None:
return 0
else:
left_length=0
right_length=0
if current.left:
left_length=self.dfs(current.left)+1
if current.right:
right_length=self.dfs(current.right)+1
self.answer=max(self.answer,left_length+right_length)
return left_length if left_length>=right_length else right_length
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.dfs(root)
return self.answer해설
먼저 왼쪽부터 가보자.
if current.left:
left_length=self.dfs(current.left)+1 아래 그림을 보면, 1번 노드는 2번 노드에게 dfs()를 호출하면서 '거리를 구해서 알려줘'라고 메시지를 보내는 것이라고 볼 수 있다. 그 동안 1번 노드는 2번 노드의 응답을 기다린다.
그런데 메시지를 받은 2번 노드는 또 왼쪽으로 갈 수 있다. 그래서 2번 노드는 4번 노드에게 거리를 구해서 알려달라고 메시지를 보낸다. 2번 노드 역시 4번 노드의 응답을 기다린다.
4번 노드는 리프 노드이므로 기저 조건에 해당한다.
if current.left==None and current.right==None:
return 0이 녀석은 거리가 0이기 때문에 단순히 0을 리턴하면 된다.
4 번 노드의 응답을 받은 2번 노드는 +1 처리를 해서 왼쪽 거리가 1이라는 것을 알게 된다.
그런데 2번 노드는 아직 오른쪽 거리를 알지 못한다. 그래서 5번 노드에게 거리좀 알아오라고 메시지를 보낸다.
2번 노드는 왼쪽과 오른쪽 모두에 대한 응답을 받았다.
따라서 아래와 같이 최대 직경을 2로 갱신한다음, 왼쪽 거리와 오른쪽 거리 중 더 긴 길이를 1번 노드에게 알려준다.
self.answer=max(self.answer,left_length+right_length)
return left_length if left_length>=right_length else right_length1번 노드는 2번 노드한테서 최대 길이가 1임을 알게 되었다. 따라서 기다림을 끝내고 +1 처리를 해준다.
1번 노드는 오른쪽도 봐야하므로 3번 노드에게 거리를 알려달라고 메시지를 보낸다.
그리고 3번 노드는 리프노드이므로 0을 리턴하게 되고, 1번 노드는 해당 응답을 받게 된다. 그러면 1번 노드는 오른쪽 길이가 1임을 알게 된다.
최대 직경을 2+1=3으로 갱신한다. 마지막으로 더 긴 길이인 왼쪽 길이를 리턴한다. (마지막에는 필요 없지만, 구조 상 어쩔 수 없다.)
다시 풀기 1회차
# 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 __init__(self):
self.answer=0
def getLength(self,current)->int:
if current.left==None and current.right==None:
return 1
else:
left,right=0,0
if current.left:
left=self.getLength(current.left)
if current.right:
right=self.getLength(current.right)
self.answer=max(self.answer,left+right)
return max(left,right)+1
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.getLength(root)
return self.answer