이진 트리의 직경
난이도 | ★
리트코드 543
문제
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: 3is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2]
Output: 1
Constraints:
The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100
[전제]
# 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: TreeNode) -> int:
문제 풀기 전 알고 갈 개념
풀이과정
풀이의 전체 과정부터 살펴보자
1) 재귀함수로 제일 마지막 노드를 찾는다
2) 마지막 노드에서 거를러 올라감
- 존재하지 않는 노드: -1 이라는 값을 부여
- 이유: 정 이진 트리 Full Binary Tree 가 아닌 대부분의 경우에는 존재하지 않는 자식 노드에 -1 을 부여해 페널티 부여
- 상태값: 리프 노드에서 현재 노드까지의 거리
- 거리(정답): 왼쪽 자식 노드의 상태값과 오른쪽 자식 노드의 상태값의 합에 2를 더한 값(없는 경우 양쪽에 -1을 부여하기 때문에)
1) 마지막 노드 찾기
def dfs(node: TreeNode) -> int:
...
left = dfs(node.left)
right = dfs(node.right)
계속 재귀 호출을 통해 왼쪽, 오른쪽의 각 잎 노드까지 DFS로 탐색
2) 마지막 노드에서 거를러 올라감
2개의 값 계산,
- 거리(정답): 최종 결과가 될 가장 긴 경로 self.longest
left + right + 2
- 상태값: 리프 노드에서 현재 노드까지의 거리
max(left, right) + 1
[방법]
- 자식 노드가 하나도 없는 경우
- left , right: 모두 -1
- 거리: 0 (left+right+2 = -1+-1+2)
- 상태값: 0 (max(left, right) + 1= -1+1=0)
- 자식 노드가 모두 존재하는 경우, (자식 노드가 둘 다 상태값이 0 일 때)
- 거리: 2 (left+right+2 = 0+0+2)
- 상태값: 1 (max(left, right) + 1= 0+1=1)
이제 [4]-> [3]-> [2]-> [1]-> [결과] 순으로 탐방 할 것이다!!!
def dfs(node: TreeNode) -> int:
...
self.longest = max(self.longest, left + right + 2)
return max(left, right) + 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:
longest: int = 0
def diameterOfBinaryTree(self, root: TreeNode) -> int:
def dfs(node: TreeNode)->int:
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
결과
내가 헤맨 이유
재귀함수를 거꾸 쓰는 법을 잘 몰랐던것 같다
재귀함수를 거꾸로 쓰려면
def dfs(node: TreeNode) -> int:
...
left = dfs(node.left)
right = dfs(node.right)
## 거꾸로 거슬러 올라가면서 하고싶은 코드
이렇게 짜면 호출했던 재귀함수다 마지막부터 실행코드를 실행한후 하나씩 없어지면서 백트레킹이 되는 것 같다!!!!!!
이제 머리에 새겨둬야겠다.. 흑…