문제 두 노드 간 값의 차이가 가장 작은 노드의 값의 차이를 출력하라. 입력 root = [4, 2, 6, 1, 3, null, null] 출력 1 노드 3과 노드 4의 값의 차이는 1이다. 입력 root = [10, 4, 15, 1, 8, null, null] 출력 2 이 경우 노드 간 값의 차이가 가장 작은 노드는 8과 10이다. 1과 4는 거리의 차이가 3이고, 4와 8은 차이가 4이지만 8과 10의 차이는 2로 최솟값이다. 코드 재귀 구조로 중위 순회 import sys class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solut..
문제 동일한 값을 지닌 가장 긴 경로를 찾아라. 입력 출력 2 입력 출력 2 코드 class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right class Solution: result: int = 0 def longestUnivaluePath(self, root: TreeNode): def dfs(node: TreeNode): if node is None: return 0 left = dfs(node.left) right = dfs(node.right) if node.left and node.left.val == node.val: left += 1 else: l..
문제 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. 다음과 같은 이진 트리가 주어졌을 때, 1 2 3 4 5 가장 긴 경로는 4 → 2 → 1 → 3 또는 5 → 2 → 1 → 3으로 3이다. 코드 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: # 리프노드의 left, right 노드를 None으로 초기화하므로 거기까지..
트리 트리는 재귀로 정의된 자기 참조 자료구조이다. 쉽게 말하면, 트리는 자식도 트리고 또 그 자식도 트리다. 즉 여러 개의 트리가 쌓아 올려져 큰 트리가 된다. 흔히 서브트리로 구성된다고 표현한다. 트리의 각 명칭 트리는 항상 루트에서부터 시작된다. 루트는 자식 노드를 가지며, 간선으로 연결되어 있다. 자식 노드의 개수는 차수라고 하며, 크기는 자신을 포함한 모든 자식 노드의 개수다. 높이는 현재 위치에서부터 리프까지의 거리, 깊이는 루트에서부터 현재 노드까지의 거리다. 트리는 그 자식도 트리인 서브 트리 구성을 띈다. 레벨은 0에서부터 시작한다. 트리는 항상 단방향이기 때문에 간선의 화살표는 생략 가능하다. 일반적으로 간선의 방향은 위에서 아래로 향한다. 그래프 vs 트리 트리는 순환 구조를 갖지 않..