[항해99] 이진 탐색 트리 (BST)

이진 탐색 트리?

부모노드 기준으로 왼쪽에는 작은 값, 오른쪽에는 큰 값을 가지는 이진트리.

탐색의 시간 복잡도는 O(logN), 치우친 경우에는 O(n) 그래서 트리가 균형잡혀있는게 중요하다!

출처 : https://www.geeksforgeeks.org/binary-search-tree-data-structure/

어떤 값을 탐색한다면, 현재 노드 기준으로 작으면 왼쪽 자식으로 가고, 크면 오른쪽 자식으로 가서 탐색을 진행한다.

 

두 이진트리의 병합

https://leetcode.com/problems/merge-two-binary-trees/

Merge Two Binary Trees - LeetCode

트리 문제들은 자식을 통해 재귀를 잘 이용하던가, 아니면 트리 형태 구조가 아닌 리스트 형태 구조에서 인덱스를 잘 활용하는 둘 중 하나인 것 같다 아무래도 .. ..

이번 문제는 전자의 경우다. 웬만하면 전자인 듯...! 

자식에 대해서 merge할 때는 재귀를 이용한다! 만약에 자식중 한 쪽이 없다면 안 비어있는 노드를 선택하는 것!

# Definition for a binary tree node.
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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:

        if root1 and root2:
            root = TreeNode(root1.val + root2.val)
            root.left = self.mergeTrees(root1.left, root2.left)
            root.right = self.mergeTrees(root1.right, root2.right)
            return root
        else: # 둘 중 하나라도 비어있으면, 안 비어있는 노드를 선택
            return root1 or root2

이진탐색트리의 범위 합

https://leetcode.com/problems/range-sum-of-bst/

Range Sum of BST - LeetCode

범위를 정해줬으니, 재귀적으로 양쪽 자식에 대해서 호출하고 그 답을 로트노드의 함수 답에 더해주면 된다.

# Definition for a binary tree node.
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 rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        ans = 0
        if root is None:
            return 0

        if high >= root.val >= low:
            ans += root.val

        ans += self.rangeSumBST(root.left, low, high)
        ans += self.rangeSumBST(root.right, low, high)
        
        return ans

이진트리의 탐색

https://leetcode.com/problems/search-in-a-binary-search-tree/

Search in a Binary Search Tree - LeetCode

탐색문제다. 서브트리를 리턴하라고하는데, 우리가 찾는 value 보다 작으먼 왼쪽, 크면 오른쪽 자식을 재귀적으로 탐색하면서 없으면 None을 리턴하고 밸류랑 같은 애면 그 서브트리를 리턴하는 방식으로 구현하면 된다.

이 문제는 쫌 중요! 이진탐색의 구조를 이해하기 좋은 문제다!

# 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 searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return None

        if root.val == val:
            return root

        if root.val > val:
            return self.searchBST(root.left, val)

        if root.val < val:
            return self.searchBST(root.right, val)

이진트리의 직렬화 역 직렬화

영어로는 serialize라고 한다고 한다. 트리 구조를 트리가 아닌 다른 형태의 구조로 바꾼 뒤 ( 이 문제의 경우 str ) 다시 돌리는 문제였다. 

str로 바꾸는 거는 재귀적으로 ""안에 담으면 해결되었는데, 다시 ""에 담긴거를 트리에 넣으려고 하니 어려웠다. 문자열을 직접 담기 보다는, 리스트로 바꾸어서 담는 방식으로 구현하였다. 

그리고 현재 문자열 안에는 root , left , right순으로 담겨있기 때문에 pop(0)하면 root left, right,순으로 나오니 그대로 루트에 재귀적으로 집어 넣으면 된다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Codec:
    def serialize(self, root):
        ans = ""
        if root is None:
            return ""

        return f"{root.val},{self.serialize(root.left)},{self.serialize(root.right)}"

    def deserialize(self, data):
        if not data:
            return None

        return self.deserialize_list(data.split(","))

    def deserialize_list(self, data):
        val = data.pop(0)
        if not val:
            return None

        root = TreeNode(val)
        root.left = self.deserialize_list(data)
        root.right = self.deserialize_list(data)

        return root


# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

Balanced Binary  Tree 균형잡힌 이진트리

https://leetcode.com/problems/balanced-binary-tree/

Balanced Binary Tree - LeetCode

문제를 잘 못 이해해서 어려움을 겪었다.

균형이 잡혔다 라는 말의 뜻은 모든 노드에 대해서 양 쪽 노드의 높이 차가 1 이하 라는 뜻이다. 

루트노드만  높이차가 1 이내이면 된다 라고 생각했는데 아니였다.

문제코드

# Definition for a binary tree node.
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 height(self, root, h):
        if root is None:
            return 0

        left= self.height(root.left, h)
        right = self.height(root.right, h)

        return max(left, right) + 1

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        left = self.height(root.left, 0)
        right = self.height(root.right, 0)

        return abs(left - right) <= 1



# 디버깅용
    def make_tree_by(self, lst, idx):
        parent = None
        if idx < len(lst):
            value = lst[idx]
            if value is None:
                return

            parent = TreeNode(value)
            parent.left = self.make_tree_by(lst, 2 * idx + 1)
            parent.right = self.make_tree_by(lst, 2 * idx + 2)
        return parent


solution_instance = Solution()
root = solution_instance.make_tree_by([1], 0)
print(solution_instance.isBalanced(root))

 

해결코드

 

여기서 주목해야 할 점은 18번 줄에 left == -1 or right == -1 인데, 이걸 처리함으로, 왼쪽이나 오른쪽이 -1이라면 따로 연산을 거치지 않고, 바로 -1을 출력해서 조금 더 시간복잡도가 좋아졌다는 것이다! 

# Definition for a binary tree node.
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 check(self, node):
        if node is None:
            return 0

        left= self.check(node.left)
        right = self.check(node.right)
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1

        return max(left, right) + 1

    def isBalanced(self, root: Optional[TreeNode]) -> bool:

        return self.check(root) != -1



# 디버깅용
    def make_tree_by(self, lst, idx):
        parent = None
        if idx < len(lst):
            value = lst[idx]
            if value is None:
                return

            parent = TreeNode(value)
            parent.left = self.make_tree_by(lst, 2 * idx + 1)
            parent.right = self.make_tree_by(lst, 2 * idx + 2)
        return parent


solution_instance = Solution()
root = solution_instance.make_tree_by([1], 0)
print(solution_instance.isBalanced(root))