리트코드 문제를 풀다 정말 괜찮은 문제를 찾아서 이렇게 올려봅니다.
이진 트리 관련 문제이고, DFS 알고리즘으로 풀 수 있습니다.
먼저 문제를 소개하고, 정답 코드를 보며 같이 분석해봅시다 🔥
문제 설명
Leetcode 543. Diameter of Binary Tree
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. 
Example 1:
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].
Example 2:
Input: root = [1,2]
Output: 1이진 트리가 주어졌을 때 가장 긴 경로를 찾는 문제입니다.
두 노드간 가장 긴 경로의 길이를 출력하면 되는 간단한 문제입니다.
처음에 저는 문제를 보자마자
"아 그럼 리프노드를 방문한다음 거기서 어떻게 저떻게 해주면 되겠구나 !?"
라는 생각을 했고, DFS 로 풀어야겠다 !! 라고 결론을 내렸습니다.
막상 문제를 풀어보니 쉽게 풀리지 않았고 정답 코드를... 봐버렸습니다 😭
못풀어서 !! 정답을 봤지만 !! 그래도 내껄로 만들면... 그러면 되는거 아니겠습니까 !!!!!!
정답 코드를 보며 차근 차근 분석을 해보겠습니다 ✌️
정답 코드
# 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:
longest = 0
def diameterOfBinaryTree(self, root: TreeNode) -> int:
def dfs(node):
if not node:
return -1
left = dfs(node.left)
right= dfs(node.right)
self.longest = max(self.longest, left + right + 2)
return max(left, right) + 1
dfs(root)
return self.longest전체적인 큰 틀은 가장 먼저 말단, 즉 리프 노드까지 탐색한 다음 부모로 거슬러 올라가면서 각각의 거리를 계산해 상태값을 업데이트하면서 다음과 같이 누적해 나가면 됩니다.
return 값
return 값은 그 노드의 값 ? 이라고 이해하면 쉽습니다.
해당 노드로부터 리프노드까지의 depth 이기도 합니다.
예를 들어, "4" 라는 값을 가진 노드는 리프 노드 입니다.
return 값은 max(left, right) + 1 로 구할 수 있고, 0 이 됩니다.
left 자식 노드와 right 자식 노드 중에서 더 큰거 (return 값이 더 큰거, depth가 더 깊은거) 하나 고르고 거기에 1을 더해주는 방식입니다.
1을 더해주는 이유는 왼쪽 노드와 오른쪽 노드 중 더 큰것을 고른 후 그 노드로 부터 해당 노드까지의 거리도 더해줘야 하기 때문입니다.
리프 노드의 자식 노드는 -1 이라는 값을 리턴하는데, 이는 None (not node, Null 값) 노드에서는 -1 을 리턴 해줘야만 리프노드에서 return 값이 0이 나오기 때문입니다.
(depth 가 0 , 리프 노드 )
또 다른 예시로는 "1" 값을 가진 노드, root 노드를 보겠습니다.
root 노드에서는 max(left, right) + 1 의 값이 3이 됩니다. (2+1)
왜냐하면 왼쪽(left)과 오른쪽(right) 중에서
( => "2"라는 값을 가진 노드와 "3"이라는 값을 가진 노드 중에서)
더 큰것은 왼쪽이고 그 값은 2 입니다. ( 해당 노드에서 부터의 depth가 2 라는 말과도 같습니다.) 2에다가 1을 더해주면 되는데, 이 때에 더해주는 1은
"2"라는 값을 가진 노드와 "1"이라는 값을 가진 root노드 사이의 길이입니다.
longest
다음은 longest 값을 보겠습니다.
longest 는 왼쪽 노드 값 + 오른쪽 노드 값 + 2 즉, max(longest, left + right + 2 ) 로 구할 수 있고 max 함수를 통해 계속해서 최대값을 갱신해 나가는 방식입니다.
예를 들어 "2" 라는 값을 가진 노드에서 longest 는 3이 됩니다. ( 0 + 1 + 2 )
왼쪽 자식은 "4"라는 값을 가진 노드인데 리프 노드이므로 0을 리턴하고
오른쪽 자식은 "5"라는 값을 가진 노드인데 밑으로 "7"이라는 자식을 하나 가지므로 1을 리턴합니다.
longest 를 쉽게 표현하면, 해당 노드에서의 왼쪽과 오른쪽을 더한 최대 길이 라고 표현이 가능한데 위의 예시에서는 "2"라는 노드를 포함했을때 왼쪽 노드 ( "4"라는 노드 ) 와 오른쪽 노드("5" 라는 노드) 를 더하고 그것들로부터 "2"라는 노드까지의
거리 각각 1,1 (합 2) 을 더해주면 됩니다.
이렇게해서 DFS 를 다 돌고나면 전역 변수인 longest 는 최대 길이 5가 되고
최종 return 값은 루트 노드에서의 최대 깊이(max depth = 3)가 됩니다.
