[코테연습] 2641. Cousins in Binary Tree II

- 해시 테이블 / DFS / 트리 / BFS / 이진 트리 문제

 

https://leetcode.com/problems/cousins-in-binary-tree-ii/description/?envType=daily-question&envId=2024-10-23

 

- 문제분석

• 이진 트리 구조:
  • 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 계층적 구조입니다.
  • 문제에서는 각 노드의 값을 사촌 노드들의 합으로 변경하는 것이 목표입니다.
• 사촌 노드의 정의:
  • 사촌 노드는 **같은 깊이(level)**에 있으면서 부모가 다른 노드들을 의미합니다.
  • 예를 들어, 루트의 자식 A와 B가 있을 때, A의 자식들과 B의 자식들은 서로 사촌 관계입니다.
• 문제의 목표:
  • 루트 노드의 값을 0으로 설정합니다.
  • 각 노드의 값을 같은 레벨에 있는 사촌 노드들의 합으로 교체합니다.
  • 즉, 해당 레벨에 있는 모든 노드의 합에서 현재 노드와 그 형제 노드의 값을 제외한 합으로 교체합니다.

- 문제풀이

1. 레벨 별 합 계산 (DFS):
   • 트리를 **깊이 우선 탐색(DFS)**으로 순회하며, 각 레벨 별 노드 값 합을 계산합니다.
   • 재귀적으로 트리를 탐색하면서 각 레벨의 값을 누적하여 기록합니다.
   • 각 레벨에서 방문한 노드의 값을 **딕셔너리(Dictionary)**에 저장합니다.
2. 트리의 모든 노드를 DFS로 재탐색하며 값 교체:
   • DFS를 사용하여 트리를 다시 순회하면서, 각 노드의 값을 사촌 노드들의 합으로 교체합니다.
   • 현재 노드의 사촌 노드 합을 계산하기 위해 다음과 같은 과정을 수행합니다:
     • 현재 노드가 위치한 다음 레벨의 전체 노드 합에서 **현재 노드의 형제 노드들(같은 부모를 공유하는 노드들)**의 값을 제외합니다.
     • 제외한 값을 현재 노드의 값으로 설정합니다.
3. 루트 노드 값 설정:
   • 루트 노드의 값은 문제의 요구사항에 따라 0으로 설정합니다.
4. 변경된 트리 반환:
   • 모든 노드를 수정한 후, 변경된 루트 노드를 반환합니다.

주요 알고리즘

• DFS(깊이 우선 탐색):
  • 첫 번째 DFS를 사용하여 레벨 별 합을 계산합니다.
  • 두 번째 DFS를 사용하여 트리의 모든 노드를 탐색하고, 사촌 노드들의 합으로 값을 변경합니다.

DFS 단계별 작업

1. 레벨 별 합 계산:
   • DFS 재귀 호출로 트리의 모든 노드를 순회하면서, 각 레벨의 합을 계산합니다.
   • 현재 노드의 깊이(레벨)를 파라미터로 전달하여 각 레벨의 값을 딕셔너리에 누적합니다.
2. 노드 값 대체:
   • 다시 DFS로 트리를 순회하면서 각 노드의 값을 업데이트합니다.
   • 현재 노드의 값을 다음 레벨의 전체 합에서 그 노드의 형제 노드들의 합을 뺀 값으로 설정합니다.

 

> java

 

class Solution {
    public TreeNode replaceValueInTree(TreeNode root) {
        Map<Integer, Integer> map = new HashMap<>();
        calculateLevelSums(root, 0, map);
        replaceNodeValues(root, map, 0);
        root.val = 0;
        return root;
    }
    void calculateLevelSums(TreeNode node, int depth, Map<Integer, Integer> map) {
        if (node == null) {
            return;
        }
        map.put(depth, map.getOrDefault(depth, 0) + node.val);
        calculateLevelSums(node.left, depth+1, map);
        calculateLevelSums(node.right, depth+1, map);
    }
    void replaceNodeValues(TreeNode node, Map<Integer,Integer> map, int depth) {
        if (node == null) {
            return;
        }
        
        int sum = 0;
        if (node.left != null) {
            sum += node.left.val;
        }
        if (node.right!= null) {
            sum += node.right.val;
        }
        if (map.get(depth+1) != null) {
            int cousinSum = map.get(depth + 1) - sum;
            if (node.left != null) {
                node.left.val = cousinSum;
            }
            if (node.right != null) {
                node.right.val = cousinSum;
            }
        }

        replaceNodeValues(node.left, map, depth+1);
        replaceNodeValues(node.right, map, depth+1);
    }
}

 

> python

 

from typing import Optional, Dict

class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None

        root.val = 0  # 루트 노드의 값을 0으로 설정

        mapper = {}
        self.calculate_level_sums(root, 0, mapper)
        self.replace_node_values(root, 0, mapper)
        return root

    def calculate_level_sums(self, node: Optional[TreeNode], depth: int, mapper: Dict[int, int]):
        if node is None:
            return
        # 레벨 별 합 계산
        mapper[depth] = mapper.get(depth, 0) + node.val
        self.calculate_level_sums(node.left, depth + 1, mapper)
        self.calculate_level_sums(node.right, depth + 1, mapper)

    def replace_node_values(self, node: Optional[TreeNode], depth: int, mapper: Dict[int, int]):
        if node is None:
            return

        # 자식 노드의 합계 계산
        total = 0
        if node.left is not None:
            total += node.left.val
        if node.right is not None:
            total += node.right.val

        # 사촌 노드의 합을 설정
        if depth + 1 in mapper:
            cousin_sum = mapper[depth + 1] - total
            if node.left is not None:
                node.left.val = cousin_sum
            if node.right is not None:
                node.right.val = cousin_sum

        # 재귀적으로 자식 노드 처리
        self.replace_node_values(node.left, depth + 1, mapper)
        self.replace_node_values(node.right, depth + 1, mapper)