6.6

main.py

"""
문제 6.6 트리 경로의 합

노드에 정수형 데이터가 있는 이진 트리가 입력으로 주어진다.
각 경로에 있는 노드의 데이터 합이 특정 값이 되는 경우가 몇 개인지 확인하라.
꼭 루트 노드에서 시작할 필요는 없으며, 시작은 부모 노드에서 자식 노드 쪽으로 이동하여 합을 만들어
나가야 한다. 자식 노드에서 위로 올라가는 경우는 없다.

### 제한 사항

1. 정수형 데이터를 가진 트리 (양수, 음수, 0)
2. 트리의 경로 조건
  - 시작은 어떤 노드나 가능
  - 다음 경로는 자식 노드만 가능함
3. sum 은 정수형 값

### 아이디어 (Brute-force)
1. 너비 우선 탐색으로 모든 노드를 방문한다.
  - 각 방문한 노드를 루트 노드로 하는 트리를 깊이 우선 탐색으로 방문하면서 경로의 합을 계산한다.
  - 경로의 합이 입력으로 주어진 값과 일치하는지를 확인한다.
2. 모든 순회가 끝나면 합이 일치했던 횟구를 반환한다.

### 아이디어 (Brute-force)
1. 깊이 우선 탐색 으로 모든 노드를 방문한다.
  - 각 방문한 노드를 루트 노드로 하는 트리를 깊이 우선 탐색으로 방문하면서 경로의 합을 계산한다.
- 경로의 합이 입력으로 주어진 값과 일치하는지 확인한다.
2. 모든 순회가 끝나면 합이 일치 했던 횟수를 반환한다.

### 아이디어 (Hash Table)
1. 해시 테이블을 생성하고 {0: 1}로 초기화 한다.
2. 깊이 우선 탐색으로 모든 노드를 방문한다.
  - (현재 루트에서 이동한 누적값 + 현재 노드 값 - SUM)이 해시 테이블에 있으면 확인하고 있으면 카운트 값을 1 증가시킨다.
  - 현재 루트에서 누적된 값 + 현재 노드 값을 키로 하고 값을 1로 하는 데이터에 해시 테이블에 추가한다.
  - 왼쪽 노드 또는 오른쪽 노드로 이동한다.
"""
from collections import deque


class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

    def __repr__(self):
        return str(self.data)


class BinaryTree:
    def __init__(self):
        self.__root = None

    @property
    def root(self):
        return self.__root

    def create_dst(self, nodes_list):
        nodes = [None if item is None else Node(item) for item in nodes_list]
        # root node
        self.__root = nodes[0]

        for index in range(1, len(nodes)):
            node = nodes[index]

            if node is not None:
                parent_index = (index - 1) // 2
                parent = nodes[parent_index]
                if not parent:
                    raise ValueError(f"Missing parent node at index {parent_index},"
                                     f"Node({node.data})")
                if index % 2:
                    parent.left = node
                else:
                    parent.right = node


def path_sum(root: Node, sum: int) -> int:
    cnt = 0

    if not root:
        return cnt

    def path_sum_sub(node: Node, target: int) -> int:
        if not node:
            return 0

        return (1 if (target - node.data) == 0 else 0) + \
               path_sum_sub(node.left, target - node.data) + \
               path_sum_sub(node.right, target - node.data)

    queue = deque()
    queue.append(root)

    while len(queue) != 0:
        q_size = len(queue)

        for _ in range(q_size):
            node = queue.popleft()

            cnt += path_sum_sub(node, sum)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return cnt


if __name__ == '__main__':
    bst = BinaryTree()

    input_datas = []
    for item in input().split(' '):
        if item == 'N':
            input_datas.append(None)
        else:
            input_datas.append(int(item))
    bst.create_dst(input_datas)

    target_sum = int(input())

    print(f'result: {path_sum(bst.root, target_sum)}')