Tree 알고리즘 정리

문제: 특정 노드에서 K 거리의 노드 찾기

• 문제 링크: All Nodes Distance K in Binary Tree
• 문제 설명: 이진 트리에서 특정 노드에서 시작해 K 거리만큼 떨어진 모든 노드를 찾아야 합니다.
• 핵심 아이디어:
  • 부모 노드 해싱:
    • 각 노드의 부모를 저장하여, 특정 노드에서 BFS를 수행할 때 위쪽 방향으로도 이동할 수 있게 구현합니다.
  • BFS 탐색:
    • 큐를 사용해 노드를 순회하며, 현재 노드의 왼쪽 자식, 오른쪽 자식, 부모 노드를 큐에 추가합니다.
  • 중복 방지:
    • visited 집합을 사용하여 중복 방문을 방지합니다.

---

풀이

from collections import deque
from typing import List, Optional

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        if not root:
            return []

        # 부모 노드를 저장할 딕셔너리
        parent = {}
        
        # 부모 노드를 해싱하여 기록
        def map_parents(node):
            if node.left:
                parent[node.left] = node
                map_parents(node.left)
            if node.right:
                parent[node.right] = node
                map_parents(node.right)
        
        map_parents(root)

        # BFS로 K 거리의 노드 탐색
        q = deque([target])
        visited = set([target])
        distance = 0
        
        while q:
            if distance == k:  # K 거리 도달 시 현재 큐에 있는 노드 값 반환
                return [node.val for node in q]
            for _ in range(len(q)):
                node = q.popleft()
                # 자식 노드와 부모 노드 순회
                for neighbor in (node.left, node.right, parent.get(node)):
                    if neighbor and neighbor not in visited:
                        visited.add(neighbor)
                        q.append(neighbor)
            distance += 1

        return []

---

시간 복잡도

• O(N): 트리의 모든 노드를 한 번씩 방문합니다.
  • 부모 노드 매핑: O(N)
  • BFS 탐색: O(N)

---

공간 복잡도

• O(N):
  • 부모 노드 딕셔너리: O(N)
  • BFS 큐와 visited 집합: O(N)

---

문제: 조상 노드와의 최대 차이 계산

• 문제 링크: Maximum Difference Between Node and Ancestor
• 문제 설명:
  • 이진 트리에서 조상 노드와 현재 노드 값의 차이 중 최대값을 계산해야 합니다.
  • 조상 노드는 현재 노드에서 루트 노드까지의 경로 상에 있는 모든 노드를 포함합니다.

---

접근법

• Bottom-Up 방식:
  • 각 노드에서 재귀적으로 하위 노드들의 최대값과 최소값을 계산.
  • 반환된 최대값, 최소값을 사용해 현재 노드와의 차이를 계산하여 최대 차이를 갱신.
• 재귀 함수 반환값:
  • 현재 서브트리의 최소값(current_min).
  • 현재 서브트리의 최대값(current_max).

---

코드

# 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
from typing import Optional

class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            nonlocal max_diff
            if not node:
                return float('inf'), float('-inf')  # 초기값: 무한대로 설정 (최소값/최대값 계산)
            
            # 좌측 및 우측 서브트리의 최소값, 최대값 계산
            left_min, left_max = dfs(node.left)
            right_min, right_max = dfs(node.right)
            
            # 현재 노드 기준 최소값과 최대값 계산
            current_min = min(node.val, left_min, right_min)
            current_max = max(node.val, left_max, right_max)

            # 최대 차이값 갱신
            max_diff = max(
                max_diff,
                abs(node.val - current_min),
                abs(node.val - current_max)
            )
            
            return current_min, current_max

        max_diff = 0
        dfs(root)  # DFS 탐색 시작
        return max_diff

---

시간 복잡도

• O(N): 트리의 모든 노드를 한 번씩 방문하며 최소값, 최대값을 계산.

공간 복잡도

• O(H): 재귀 호출 스택의 최대 깊이 (H는 트리의 높이).

---

문제: 특정 노드에서 K 거리의 노드 찾기

• 문제 링크: All Nodes Distance K in Binary Tree
• 문제 설명: 특정 노드에서 K 거리만큼 떨어진 모든 노드를 찾아야 합니다.
• 핵심 아이디어:
  • 부모 노드 해싱: 부모 노드를 해시 테이블에 저장하여 BFS 중 위로도 탐색할 수 있게 구현합니다.
  • BFS 탐색 시, 왼쪽/오른쪽 자식 노드와 부모 노드를 큐에 추가합니다.
  • 중복 처리: 방문했던 노드는 visited 집합에 추가하여 중복 순회를 방지합니다.

코드

from collections import deque
from typing import List, Optional

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        if not root:
            return []

        # 부모 노드 저장
        parent = {}
        def map_parents(node):
            if node.left:
                parent[node.left] = node
                map_parents(node.left)
            if node.right:
                parent[node.right] = node
                map_parents(node.right)
        
        map_parents(root)

        # BFS 탐색
        q = deque([target])
        visited = set([target])
        distance = 0
        
        while q:
            if distance == k:
                return [node.val for node in q]
            for _ in range(len(q)):
                node = q.popleft()
                for neighbor in (node.left, node.right, parent.get(node)):
                    if neighbor and neighbor not in visited:
                        visited.add(neighbor)
                        q.append(neighbor)
            distance += 1

        return []

시간 복잡도

• O(N): 트리의 모든 노드를 한 번씩 순회합니다.
  • 부모 노드 매핑: O(N)
  • BFS 탐색: O(N)

공간 복잡도

• O(N):
  • 부모 노드 해시 테이블: O(N)
  • BFS 큐와 visited 집합: O(N)

---

문제: 가장 깊은 노드들의 가장 작은 공통 부모 노드 찾기

• 문제 링크: Smallest Subtree with All the Deepest Nodes
• 문제 설명: 가장 깊은 레벨에 있는 모든 노드를 포함하는 가장 작은 서브트리를 반환해야 합니다.
• 핵심 아이디어:
  • BFS로 가장 깊은 노드 탐색: BFS를 사용해 가장 깊은 노드들을 찾습니다.
  • 부모 해싱: 각 노드의 부모를 해시 테이블에 저장합니다.
  • 위로 탐색: 가장 깊은 노드들의 공통 부모를 찾기 위해 위로 탐색하며 공통 부모를 찾습니다.

코드

from collections import deque
from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        # 부모 노드 저장
        parent = {}
        deepest_nodes = []
        
        # BFS로 가장 깊은 노드 찾기
        q = deque([root])
        while q:
            deepest_nodes = list(q)
            for _ in range(len(q)):
                node = q.popleft()
                if node.left:
                    parent[node.left] = node
                    q.append(node.left)
                if node.right:
                    parent[node.right] = node
                    q.append(node.right)

        # 가장 깊은 노드들의 공통 부모 탐색
        while len(deepest_nodes) > 1:
            deepest_nodes = list(set(parent[node] for node in deepest_nodes))

        return deepest_nodes[0]

시간 복잡도

• O(N): BFS와 공통 부모를 찾는 과정에서 트리의 모든 노드를 한 번씩 방문합니다.

공간 복잡도

• O(N):
  • 부모 해시 테이블: O(N)
  • BFS 큐와 깊은 노드 리스트: O(N)

---

문제: Preorder와 Postorder로 트리 생성하기

• 문제 링크: Construct Binary Tree from Preorder and Postorder Traversal
• 문제 설명: 주어진 Preorder와 Postorder 배열로 이진 트리를 구성해야 합니다.
• 핵심 아이디어:
  • Preorder와 Postorder 비교:
    • Preorder: 부모 → 왼쪽 자식 → 오른쪽 자식
    • Postorder: 왼쪽 자식 → 오른쪽 자식 → 부모
  • 재귀적 접근:
    • Preorder 배열의 첫 번째 값은 부모 노드 값입니다.
    • Preorder의 두 번째 값은 왼쪽 서브트리의 루트 값이며, Postorder에서 이 값의 인덱스를 통해 왼쪽 서브트리 크기를 계산합니다.
    • 이를 기반으로 왼쪽과 오른쪽 서브트리를 재귀적으로 구성합니다.

코드

from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def build(preorder, postorder):
            if not preorder or not postorder:
                return None
            
            root = TreeNode(preorder[0])
            
            if len(preorder) == 1:
                return root
            
            # 왼쪽 서브트리 크기 계산
            left_root_val = preorder[1]
            left_subtree_size = postorder.index(left_root_val) + 1
            
            # 왼쪽과 오른쪽 서브트리 재귀 생성
            root.left = build(preorder[1:1 + left_subtree_size], postorder[:left_subtree_size])
            root.right = build(preorder[1 + left_subtree_size:], postorder[left_subtree_size:-1])
            
            return root
        
        return build(preorder, postorder)

시간 복잡도

• O(N): 각 노드에 대해 Preorder와 Postorder를 탐색합니다.

공간 복잡도

• O(N):
  • 재귀 호출 스택 공간: O(N)

---

문제: 트리의 홀수 레벨에 있는 노드 값을 반대로 뒤집기

• 문제 링크: Reverse Odd Levels of Binary Tree
• 문제 설명: Perfect Binary Tree에서 홀수 레벨에 있는 노드 값을 뒤집습니다.
• 핵심 아이디어:
  • BFS로 트리의 레벨을 순차적으로 탐색.
  • 홀수 레벨에 도달하면 해당 레벨의 노드 값을 뒤집음.
  • DFS 활용 가능: 조건이 Perfect Binary Tree이므로 DFS 방식으로도 해결 가능.
    • 왼쪽 자식의 왼쪽 자식 ↔ 오른쪽 자식의 오른쪽 자식.
    • 왼쪽 자식의 오른쪽 자식 ↔ 오른쪽 자식의 왼쪽 자식.

코드

BFS 방식

from collections import deque

class Solution:
    def reverseOddLevels(self, root: TreeNode) -> TreeNode:
        def reverse(nodes):
            i, j = 0, len(nodes) - 1
            while i < j:
                nodes[i].val, nodes[j].val = nodes[j].val, nodes[i].val
                i, j = i + 1, j - 1

        q = deque([root])
        level = 0

        while q:
            level_size = len(q)
            nodes = []

            for _ in range(level_size):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                    q.append(node.right)
                    nodes.append(node.left)
                    nodes.append(node.right)

            if level % 2 == 1:
                reverse(nodes)

            level += 1

        return root

DFS 방식

class Solution:
    def reverseOddLevels(self, root: TreeNode) -> TreeNode:
        def dfs(left, right, level):
            if not left or not right:
                return
            if level % 2 == 1:
                left.val, right.val = right.val, left.val
            dfs(left.left, right.right, level + 1)
            dfs(left.right, right.left, level + 1)

        dfs(root.left, root.right, 1)
        return root

시간 복잡도

• O(N): 모든 노드를 한 번씩 방문.

공간 복잡도

• O(H): DFS 또는 BFS 큐의 공간 사용량 (H는 트리의 높이).

---

문제: 트리에서 가장 합이 큰 경로 찾기

• 문제 링크: Most Profitable Path in a Tree
• 문제 설명: a는 아무 leaf로, b는 a의 출발점으로 간다고 한다. a와 b가 동시에 도착하면 보상을 나눠서 가지고 이미 b가 지나간 노드면 보상을 받지 않는다.
• 핵심 아이디어:
  • tree이기 때문에 b->a 출발점으로 가는 경로는 반드시 하나다
  • 먼저 이 경로를 찾아햐하고 backtracking으로 b에서 거쳐가는 노드들의 level을 같이 기록한다. ex) {노드: n번째}
  • a와 b가 노드 k에 동시에 도착: 기록에 노드k가 있고 a도 n번째에 도착
    • 보상/2
  • b가 먼저 노드 k에 동시에 도착: 기록에 노드k가 있고 a가 m > n번째에 도착
    • 보상 없음
  • a가 먼저 노드 k에 동시에 도착: 기록에 노드k가 있고 a가 m < n n번째에 도착
    • 풀 보상
  • b->a 경로에 노드 k가 없음
    • 풀 보상

class Solution:
    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
        def dfs_bob(node, level):
            visited[node] = True
            if node == 0:
                return True 
            for next_node in tree[node]:
                if not visited[next_node]:
                    bob_path[next_node] = level + 1
                    if dfs_bob(next_node, level + 1):  
                        return True
                    del bob_path[next_node]
            return False
        def dfs_alice(node,level,total):
            nonlocal bob_path, ans
            visited[node]=1
            if node in bob_path:
                if bob_path[node] == level:
                    total += amount[node]//2
                elif bob_path[node] > level:
                    total += amount[node]
            else:
                total += amount[node]
            is_leaf = True
            for next_node in tree[node]:
                if not visited[next_node]:
                    is_leaf = False
                    dfs_alice(next_node,level+1,total)
            if is_leaf:
                ans = max(ans,total)
                    
        tree = defaultdict(list)
        for u,v in edges:
            tree[u].append(v)
            tree[v].append(u)

        visited = [False] * len(amount)
        bob_path = {bob: 0}
        dfs_bob(bob, 0)

        visited = [False] * len(amount)
        ans = float('-inf')
        dfs_alice(0,0,0)

        return ans

시간 복잡도

O(N)

• O(N): dfs
• O(N): 트리 생성

공간 복잡도

O(N)

• O(N): 트리 생성 딕셔너리
• O(N): 방문 노드
• O(N): bob 경로 딕셔너리
• O(H): 트리 높이 만큼 dfs 재귀 호출 스택 사용

---

문제: cycle sort

• 문제 링크: Minimum Number of Operations to Sort a Binary Tree by Level
• 문제 설명:
• 각 이진 트리의 레벨(층)마다 오름차순으로 정렬할 때 최소 swap 횟수를 구해야하는 문제
• 핵심 아이디어:
  • bfs로 각 층 방문
  • 최소 swap 수를 구하기 위해서 cycle sort를 사용한다
  • 정렬된 리스트와 원본 리스트를 비교하며 swap한다
  • 각 값의 현재 인덱스를 추적하기 위해 {값: 인덱스} 딕셔너리를 사용. 현재 위치와 목표 위치를 쉽게 대조할 수 있음.

# 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 minimumOperations(self, root: Optional[TreeNode]) -> int:
        def sort(lst):
            target = sorted(lst)
            swap = 0
            pos = {val: idx for idx,val in enumerate(lst)}
            for i in range(len(lst)):
                if lst[i]!=target[i]:
                    swap+=1
                    lst[pos[target[i]]] = lst[i]
                    pos[lst[i]] = pos[target[i]]
                    lst[i] = target[i]
                    pos[target[i]] = i
                    
            return swap

        def bfs(root):
            q = deque([root])
            total = 0
            while q:
                cur_level = []
                for _ in range(len(q)):
                    node = q.popleft()
                    cur_level.append(node.val)
                    if node.left:
                        q.append(node.left)
                    if node.right:
                        q.append(node.right)
                total += sort(cur_level)
            return total
        return bfs(root)

시간 복잡도

O(N Log N)

• O(N): bfs
• O(N Log N): 노드 N개 일 때 레벨 수는 약 Log N. 트리의 모든 레벨에서 정렬

공간 복잡도

O(N)

• O(N): 트리 생성 딕셔너리
• O(N): 방문 노드
• O(N): 리스트 딕셔너리

---

문제: cycle sort

• 문제 링크: 2476. Closest Nodes Queries in a Binary Search Tree
• 문제 설명:
• 루트 노드와 양의 정수로 이루어진 쿼리 배열이 주어집니다.
  쿼리 queries[i]에 대해
  • mini: queries[i]보다 작거나 같은 트리의 가장 큰 값을 찾습니다. 없다면 -1을 반환합니다.
  • maxi: queries[i]보다 크거나 같은 트리의 가장 작은 값을 찾습니다. 없다면 -1을 반환합니다.
    반환값은 각 쿼리마다 [mini, maxi]로 이루어진 2D 배열이어야 합니다.
• 핵심 아이디어
• BST를 중위 순회하여 정렬된 배열 tree로 변환합니다.
• 정렬된 배열을 이진 탐색하여 쿼리 값 q에 대해 mini와 maxi를 탐색합니다.

# 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 closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
        def tree_to_array(root):
            nonlocal tree
            if not root:
                return
            tree_to_array(root.left)
            tree.append(root.val)
            tree_to_array(root.right)

        tree = [] 
        tree_to_array(root)
        print(tree)
        ans = []
        for q in queries:
            s=0
            f=len(tree)-1
            mid = (s+f)//2
            flag = False
            while s<=f:
                mid = (s+f)//2
                if tree[mid] == q:
                    ans.append([q,q])
                    flag = True
                    break
                elif tree[mid] > q:
                    f = mid-1
                else:
                    s = mid+1
            if not flag:
                if tree[mid] < q:
                    if mid < len(tree) - 1:
                        ans.append([tree[mid],tree[mid+1]])
                    else:
                        ans.append([tree[mid],-1])
                elif tree[mid] > q:
                    if mid > 0:
                        ans.append([tree[mid-1],tree[mid]])
                    else:
                        ans.append([-1,tree[mid]])
        return ans
        

시간 복잡도:

O(N + M log N)

O(N): 트리를 배열로 변환 (노드 개수 N)
O(log N): 각 쿼리당 이진 탐색

공간 복잡도:

O(N): 배열 tree에 노드를 저장