심화 과정 8 일차

1. 자료구조 및 알고리즘 8일차 수강하기

 - 트리

 

 - 이진트리

 

2. 새롭게 알게된 지식

 - 이진 트리란?

   1. 모두가 연결되어 있는 그래프

   2. 정점(Node) 의 갯수 = 간선의 갯수 + 1 ( 그래프 내 사이클이 발생하지 않음 ) 

 

- 일반적으로 트리에 관한 문제는 DFS 가 적합 (부모 자식관의 관계 및 Sub tree 부터 해결해서 전체를 해결)

 

- Rooted Tree

 

 

과제 1 : 이진 트리의 직경https://leetcode.com/problems/diameter-of-binary-tree

LeetCode - The World's Leading Online Programming Learning Platform

 

 - 접근 : 

 

 

 - EX>

 

 

 

 

 

 

 - 코드 구현 : 

 

 

 

과제 2 : 트리의 부모 찾기 https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

 - 접근 : 

 

 양방향 노드 설정 후 루트 노드 부터 시작하여 방문 여부를 확인하면서 끝까지 부모 노드 기록

 

 - 코드 구현 : 

import sys
from collections import defaultdict, deque

class Solution:
    def __init__(self):
        self.input = sys.stdin.readline
        self.output = sys.stdout.write

    def bfs(self, start, n, tree):
        res = [0] * (n + 1)
        Q = deque()
        Q.append((tree[start], start))

        while Q :
            
            # 노드 정보 가져오기
            linked_node, parent_value = Q.popleft()

            for now in linked_node:
                
                #방문한 경우 다음으로 넘어가기
                if res[now]:
                    continue

                """ 출력을 2부터 순서대로 해야 하므로
                    리스트의 인덱스에 부모 정보 저장 
                    EX> res[2] -> 4 ( 2 노드의 부모 노드 =  4)
                """
                res[now] = parent_value
                Q.append((tree[now], now))

        return res

    def run(self):
        n = int(self.input().rstrip())
        tree = defaultdict(list)

        for _ in range(n-1):
            a, b = map(int, self.input().split(' '))
            tree[a].append(b)
            tree[b].append(a)

        answer = self.bfs(1, n, tree)

        for i in range(2, n+1):
            self.output(str(answer[i])+'\n')

s = Solution()
s.run()

 

 

 

과제 3 : Range Sum of BST : https://leetcode.com/problems/range-sum-of-bst/  

LeetCode - The World's Leading Online Programming Learning Platform

 

 - 접근 : 

 트리 전체를 순회 하면서 현재 노드의 값이 주어진 조건에 해당하면 더한 후 출력 ( BFS 로 구현 )

 

 - 코드 구현 : 

 

 

 

 

과제 4 : Search in a Binary Search Tree : https://leetcode.com/problems/search-in-a-binary-search-tree/

LeetCode - The World's Leading Online Programming Learning Platform

 

 - 접근 : 

 

  트리를 순회하면서 찾고자 하는 값의 노드가 나오면 출력 ( BFS )

 

 - 코드 구현 : 

 

 

 

 

과제 5 : 균형 이진 트리 https://leetcode.com/problems/balanced-binary-tree

LeetCode - The World's Leading Online Programming Learning Platform

 

 - 접근 : 

과제 1 : 이진 트리의 직경 에서 최대 길이를 결과로 들고 다니지 않고 좌우 대칭 결과를 넣으면 된다.

 

시간 복잡도를 줄이기 위하여 자식 노드 중 1개라도 False 가 나오면 결과값으로 출력

 

 -  코드 구현 :

 

 

 

  

과제 6 : 트리 : https://www.acmicpc.net/problem/1068

1068번: 트리

 

 -접근 : 

  트리를 형성할 때, 삭제할 노드를 자식에 포함하지 않고, 트리를 순회하여 리프 노드의 개수를 출력

 

 - 코드 구현 : 

 

import sys
from collections import defaultdict, deque

class Solution:
    def __init__(self):
        self.input = sys.stdin.readline
        self.output = sys.stdout.write

    def bfs(self, start, tree):
        Q = deque()
        Q.append(tree[start])
        res = 0

        while Q :
            now = Q.popleft()
            for n in now:
                if tree[n]:
                    Q.append(tree[n])
                    continue

                # 리프 노드인 경우 결과 + 1
                res += 1

        return res


    def run(self):
        N = int(self.input().rstrip())
        input_data = [int(i) for i in self.input().split(' ')]
        del_num = int(self.input().rstrip())
        tree = defaultdict(list)
        #삭제할 노드를 제외하고 트리로 저장
        for i, num in enumerate(input_data):
            if i == del_num: 
                continue

            tree[num].append(i)

        self.output(str(self.bfs(-1, tree)) + '\n')

s = Solution()
s.run()