[2024] day 199. Leetcode 2096. Step-By-Step Directions From a Binary Tree Node to Another
코딩테스트
2024년부터 새롭게 다시 시작하는 코딩테스트
2024년 7월 16일 (화)
Leetcode daily problem
2096. Step-By-Step Directions From a Binary Tree Node to Another
Problem
n개의 노드가 있는 이진 트리의 루트가 제공되고, 각 노드에는 1부터 n까지의 값이 고유하게 할당된다. 시작 노드 s의 값을 나타내는 정수 startValue와 대상 노드 t의 값을 나타내는 다른 정수 destValue가 제공 될 때 노드 s에서 시작하여 노드 t에서 끝나는 최단 경로를 찾는다.
대문자 'L', 'R', 'U'만으로 구성된 문자열과 같은 경로의 단계별 방향을 반환한다. 각 문자는 특정 방향을 나타내는데,
- 'L'은 노드에서 왼쪽 자식 노드로 이동하는 것을 의미
- 'R'은 노드에서 오른쪽 자식 노드로 이동하는 것을 의미
- 'U'는 노드에서 상위 노드로 이동하는 것을 의미 한다.
노드 s에서 노드 t까지의 최단 경로의 단계별 방향을 반환한다.
Solution
LCA + DFS
트리의 루트에서 두 노드로 가는 경로를 추적하면, 이 경로들은 특정 지점까지는 공통된 부분을 공유하며 그 이후로는 갈라진다. 이 마지막 교차 지점이 가장 낮은 공통 조상(최저 공통 조상, LCA)이다. 두 노드를 연결하는 경로는 반드시 이 LCA를 지나야 한다.
시작 노드와 목적지 노드 사이의 경로를 시작 노드에서 LCA로 가는 경로와 LCA에서 목적지 노드로 가는 경로로 나눈다. 시작 노드에서 LCA로 가는 경로는 모두 자식 노드에서 부모 노드로 이동하므로 방향은 "U"로만 이루어져 있다.
이 경로들을 찾기 위해, LCA에서 시작하여 대상 노드로 이동하는 깊이 우선 탐색(DFS)을 사용한다. 처음에는 경로에 'L'을 추가하여 왼쪽 서브트리를 탐색하고 대상 노드를 찾으면 즉시 반환한다. 찾지 못한 경우, 'L'을 'R'로 대체하여 오른쪽 서브트리를 탐색한다. 대상 노드를 두 서브트리에서 모두 찾지 못하면 부모 노드로 되돌아간다. 이 재귀 과정은 대상 노드를 찾을 때까지 반복한다.
이제 LCA에서 시작 노드와 목적지 노드로 가는 경로를 알게되면 경로를 조합할 수 있다. LCA에서 시작 노드로 가는 경로를 "U"로 변환하고, 이를 목적지 노드로 가는 경로 앞에 붙인다. 이 결과는 이진 트리에서 시작 노드에서 목적지 노드까지의 단계별 방향을 나타낸다.
Code
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
def findLCA(root, start, destination):
if not root:
return None
if root.val == start or root.val == destination:
return root
left = findLCA(root.left, start, destination)
right = findLCA(root.right, start, destination)
if left and right:
return root
return left if left else right
def findPath(root, val, path):
if not root:
return False
if root.val == val:
return True
path.append('L')
if findPath(root.left, val, path):
return True
path.pop()
path.append('R')
if findPath(root.right, val, path):
return True
path.pop()
return False
lca = findLCA(root, startValue, destValue)
pathToStart, pathToDest = [], []
findPath(lca, startValue, pathToStart)
findPath(lca, destValue, pathToDest)
return 'U' * len(pathToStart) + ''.join(pathToDest)Complexicity
시간 복잡도
이진 트리에서 두 노드의 공통 조상을 찾는 findLCA 함수에서 이진 트리의 모든 노드를 한번씩 방문하므로 시간 복잡도는 트리의 노드 수인 n에 따라 O(n)이 소요된다.
또한 특정 노드까지의 경로를 찾는 findPath 함수 또한 최악의 경우 트리의 모든 노드를 방문해야 할 수 있어 시간복잡도는 O(n) dlek.
getDirections 함수에서 findLCA 함수가 한 번 호출되고, findPath 함수가 두 번 호출되고 각 함수의 호출이 독립적으로 발생해 전체 시간 복잡도는 각 함수의 시간복잡도의 합이다 O(n) + 2*O(n) 으로 O(n) 이다.
공간 복잡도
이진 트리에서 두 노드의 공통 조상을 찾는 findLCA 함수는 재귀적으로 호출되므로 호출 스택의 깊이는 트리의 높이에 비례한다. 균형 잡힌 이진트리라면 O(logn)이지만, 균형잡히지 않았다면 높이는 O(n)이다. 트리의 높이를 n이라고 한다면 공간복잡도는 O(n)이다.
특정 노드의 경로를 찾는 findPath 함수 또한 재귀적으로 호출되고 스택의 깊이는 트리의 높이에 비례한다. 공간복잡도는 O(n)이다.
즉 전체 공간복잡도는 O(n) + 2*O(n) = O(n)이다.
