TIL_220524_이진트리 알고리즘

https://leetcode.com/problems/merge-two-binary-trees/
두 트리 병합

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
'''
답안
Queue를 쓰는 방식을 예상했지만 더 간단함
'''
class Solution:
    def mergeTreesMyway(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:

        if root1 is None:
            return root2
        if root2 is None:
            return root1
        root1.val += root2.val

        root1.left = self.mergeTrees(root1.left,root2.left)
        root1.right = self.mergeTrees(root1.right,root2.right)

        return root1

https://leetcode.com/problems/range-sum-of-bst/
BST의 범위 합계

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


class Solution:
    sum: int = 0
    '''
    개인 답안,
    트리에 조금 익숙해진 느낌임
    다만 low와 high를 계속 달고 다니니 성능우려가 있음
    더 좋은 방안이 있을 꺼 같음
    '''
    def rangeSumBSTMyway(self, root: Optional[TreeNode], low: int, high: int) -> int:
        def sumDfs(node: Optional[TreeNode]):
            if node is None:
                return
            if low <= node.val <= high:
                self.sum += node.val
            sumDfs(node.left)
            sumDfs(node.right)
        sumDfs(root)
        return self.sum

    '''
    답안
    마찬가지로 dfs를 이용
    하지만 low를 통한 비교로 가지 치기를 했음
    모든 노드를 확인하는게 아니라 성능이 개선됨
    '''
    def rangeSumBSTRecursive(self, root: Optional[TreeNode], low: int, high: int) -> int:
        def dfs(node):
            nonlocal ans
            if node:
                if low <= node.val <= high:
                    ans += node.val
                if low < node.val:
                    dfs(node.left)
                if node.val < high:
                    dfs(node.right)

        ans = 0
        dfs(root)
        return ans

    '''
    재귀가 아닌 Queue 형태를 사용함
    필요없는 경우도 가지치기를 하니,
    성능이 제일 좋은 방안 같음
    '''
    def rangeSumBSTIterative(self, root: Optional[TreeNode], low: int, high: int) -> int:
        ans = 0
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                if low <= node.val <= high:
                    ans += node.val
                if low < node.val:
                    stack.append(node.left)
                if node.val < high:
                    stack.append(node.right)
        return ans

https://leetcode.com/problems/search-in-a-binary-search-tree/
바이너리 서치 트리에서 찾기

'''

아까 더해줬던 방식 처럼 하면 될 듯 함,
다만 이번에는 성능을 위해 재귀 대신 Queue를 사용
'''

# Definition for a binary tree node.
from collections import deque


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:
    '''
    개인 답안
    구현은 했지만 성능 지표는 그리 좋게 나오지는 않는 듯 함
    아마도 if문으로 가지 치기를 안해서 그런 듯함

    val을 기준으로 left, right 작은지 여부를 확인하면 되니,
    한번 개선진행

    if문 넣어봤는데...별로 그다지 큰 변동은 없음

    '''
    def searchBSTMyway(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if node:
                if node.val == val:
                    return node
                else:
                    if node.val > val:
                        queue.append(node.left)
                    else:
                        queue.append(node.right)
        return

    '''
    답안
    Queue를 괜히 사용한 느낌임
    어차피 한 방향으로만 흐르니, 재귀를 따라가면 되는 일이었음
    큐를 안쓰니 메모리는 절약되고 성능도 좋음
    '''
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root : return None
        else :
            if root.val == val :
                return root
            elif root.val > val :
                return self.searchBST(root.left, val)
            elif root.val < val :
                return self.searchBST(root.right, val)


    '''
    더 개선된 버전
    재귀없이 while 처리함
    '''
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        cur_node = root
        while cur_node:
            if cur_node.val == val:
                return cur_node
            elif cur_node.val < val:
                cur_node = cur_node.right
            else:
                cur_node = cur_node.left

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
이진 트리 직렬화 및 역직렬화

'''

초기 생각
문제가 잘 이해가 안됬는데,
트리를 받으면 이를 문자열 형태로 반환해 출력하라는 뜻...
'''
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
import collections
from collections import deque

'''답안
중요한 점은 직렬화가 아니었음
# 처리를 해서 정리를 하면 되는 걸 난 시간만 끌다가 망함

'''
class Codec:

    def serialize(self, root: TreeNode) -> str:
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        queue = collections.deque([root])
        result = ['#']
        # 트리 BFS 직렬화
        while queue:
            node = queue.popleft()
            if node:
                queue.append(node.left)
                queue.append(node.right)

                result.append(str(node.val))
            else:
                result.append('#')
        return ' '.join(result)

    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        # 예외 처리
        if data == '# #':
            return None

        nodes = data.split()

        root = TreeNode(int(nodes[1]))
        queue = collections.deque([root])
        index = 2
        while queue:
            node = queue.popleft()
            if nodes[index] is not '#':
                node.left = TreeNode(int(nodes[index]))
                queue.append(node.left)
            index += 1

            if nodes[index] is not '#':
                node.right = TreeNode(int(nodes[index]))
                queue.append(node.right)
            index += 1

        return root

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

'''

Queue를 사용해서 처음 루트에서 검증을 하고, 이후에 while로 양쪽을 따로 반복처리
기존에 사용한 깊이 구하기 루틴을 양쪽으로 하는 차이인듯 함
'''
# Definition for a binary tree node.
import collections
from typing import Optional


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

'''
작성하다 포기하고 답안 봄
내가 너무 로직을 이상하게 짠듯함
차라리 쉽게 갔으면 좋았을텐데,  재귀를 안하고 Queue로 했다가 피봄
'''
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        queue = collections.deque([root])

        node = queue.popleft()
        count_left = 0
        count_right = 0
        queue_left = collections.deque([node.left])
        queue_right = collections.deque([node.right])
        while queue_left or queue_right:
            if queue_left:
                count_left += 1
                for _ in range(len(queue_left)):
                    node_left = queue_left.popleft()
                    if node_left:
                        if node_left.left:
                            queue_left.append(node_left.left)
                        if node_left.right:
                            queue_left.append(node_left.right)

            if queue_right:
                count_right += 1
                for _ in range(len(queue_right)):
                    node_right = queue_right.popleft()
                    if node_right:
                        if node_right.left:
                            queue_right.append(node_right.left)
                        if node_right.right:
                            queue_right.append(node_right.right)
            if abs(count_right - count_left) >= 2:
                return False
        return True

    '''
    답안: 재귀 구조로 높이 차이 계산
    계산의 리턴 값은 숫자, 숫자를 중첩가능
    재귀함수 내에서 left, right 등의 별도 변수를 잡고
    해당 값을 max로 끌고 가면 계속 이어서 리턴이 가능함
    '''
    def isBalanced(self, root:TreeNode) -> bool:
        def check(root):
            if not root:
                return 0

            left = check(root.left)
            right = check(root.right)

            if left == -1 or \
                right == -1 or \
                abs(left - right) > 1:
                return -1
            return max(left, right) + 1

        return check(root) != -1

https://leetcode.com/problems/minimum-height-trees/
최소 트리 높이

'''
초기 생각
일단 리스트가 제공되지 않음
즉 뭔가....수식을 기반으로 처리해야함

일단 노드들은 전부 돌려야함...

고민만 하다가 일단 답을 봄
생소한 개념이라 이해하는데 시간이 필요했음
'''
import collections
from typing import List


class Solution:
    '''
    답안
    그래프를 만들기 위해서 딕셔너리에 키와 값을 교차해 넣는 방식은 배워야 할 것 같음
    '''
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        # 노드 개수가 1보다 작거나 같으면 처리할 필요가 없어 0을 리턴
        if n <= 1:
            return [0]

        # 양방향 그래프 구성
        # 내부 요소들의 간선을 표현하기 위해서 딕셔너리로 넣어줌
        graph = collections.defaultdict(list)
        for i, j in edges:
            # 서로에 대한 연결을 알려주기 위해서 키와 값을 나눠서 교차해서 넣어줌
            graph[i].append(j)
            graph[j].append(i)

        # 첫 번째 리프 노드 추가
        leaves = []
        for i in range(n + 1):
            # 그래프에서 노드가 1개 뿐인 요소는 말단 부분
            if len(graph[i]) == 1:
                # 제거를 위해 leaves에 추가
                leaves.append(i)

        # 루트 노드만 남을 때까지 반복 제거
        while n > 2:
            # 제거 대상은 말단 부분
            n -= len(leaves)
            new_leaves = []
            # 담아둔 말단 부분을 제거 하기 위해 꺼냄
            for leaf in leaves:
                # 그래프에서 말단의 키를 이용해 요소를 제거
                neighbor = graph[leaf].pop()
                # 해당 제거한 말단에 값(연결된 키)를 꺼내서 다시 그래프에서 해당 연결된 키에서 삭제된 값을 찾아 같이 제거
                graph[neighbor].remove(leaf)

                # 연결된 값을 제거 했는데 해당 노드에 이제 남은 요소의 개수가 1인 경우 새로운 말단으로 인식
                # 새로운 말단을 신규 대상에 저장
                if len(graph[neighbor]) == 1:
                    new_leaves.append(neighbor)
            # 만들어진 신규 말단 리스트는 기존 말단 리스트에 넣고 다시 반복을 진행해 처리 대상이 됨
            leaves = new_leaves
        # 말단이 계속 처리되며 남은 요소들이 반환됨
        return leaves

https://www.acmicpc.net/problem/1068
트리

'''
답안
일단 삭제 대상과 배열을 재귀로 돌림
삭제 대상의 값을 -2로 바꿔버림
또한 삭제 대상의 값을 가지고 있는(즉, 부모로 삼고 있는)
요소가 존재하면 해당 값을 DFS에 넣고 돌려버림
결국 삭제 대상인 값들은 전부 -2가 됨

재귀가 끝나고, 배열중 값이 -2 즉 삭제된 값이 아니고,
전체 배열만큼 돌리면서 index 값이 다른 곳에서 참조되지 않은(즉 자식이 없는)
요소를 찾는 만큼 count를 +1해줌
즉 삭제된 요소와 자식이 있는 요소를 제외한 나머지 요소가 count됨...

좀더 수식을 생각하고, 요소끼리의 관계성을 따져봐야했음
그랫다면 좀더 잘 풀었을 텐데
괜히 복잡하게 진행하려했음

'''

def dfs(num, arr):
    arr[num] = -2
    for i in range(len(arr)):
        if num == arr[i]:
            dfs(i, arr)

n = int(input())
arr = list(map(int, input().split()))
k = int(input())
count = 0

dfs(k, arr)
count = 0
for i in range(len(arr)):
    if arr[i] != -2 and i not in arr:
        count += 1
print(count)

[오늘의 고민]
쉬운 알고리즘 문제는 어느정도 풀 수 있었지만
심화로 넘어가면서 초기에 방향을 잘못 잡고 삽질하다가 결국 답지를 보는 경우가 많음
삽질하는 만큼 좀 결과가 나왔으면 좋았을텐데,
차라리 시간이 더 들더라도 잘못 했다는걸 알았을때 다른 방향으로 도전하는 방법을 생각해 봐야겠음
지금도 자료구조에 익숙해지는건 맞지만,
결과를 내면 더 익숙해지지 않을까 고민이 생김

아니면 조금 빨리 끝내더라도, 시간을 정해서 답을 보고 이해한다음
자바 스크립트와 cs에 좀더 투자를 하는게 나아 보임