greentea31's Note

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

풀이 과정

특정 트리의 전위 순회 결과와 중위 순회 결과를 입력으로 받아서, 원래 트리를 복원시키는 문제이다.

전위, 중위, 후위 순회의 결과중 2가지 정보로 원래 트리를 복원 시킬 수 있다고 알려져있다. 1가지 정보로는 자식 노드가 왼쪽에 붙을지 오른쪽에 붙을지 알 수 없으므로 판별할 수 없다.

문제에서 보이듯이 이 트리의 전위 순회와 중위 순회 결과는

전위 = [3, 9, 20, 15, 7]

중위 = [9, 3, 15, 20, 7]

이다. 전위 순회의 결과를 앞에서 읽어나가면서 중위 순회의 결과를 읽은 값 기준으로 왼쪽과 오른쪽으로 분할 정복하는 방법으로 문제를 해결할 수 있다.

소스 코드

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if inorder:
            index = inorder.index(preorder.pop(0))  # deque의 popleft()를 쓰는게 더 빠름
            node = TreeNode(inorder[index])
            node.left = self.buildTree(preorder, inorder[0:index])
            node.right = self.buildTree(preorder, inorder[index+1:])
            return node

https://leetcode.com/problems/minimum-distance-between-bst-nodes/

풀이 과정

이진 탐색 트리의 임의의 두 노드의 차의 최소값을 구하는 문제이다.

이진 탐색 트리의 특성상 특정 노드의 왼쪽 서브트리에는 자신보다 작은 노드 값을 가진 노드들만이 존재하고, 오른쪽 서브트리에는 큰 노드 값을 가진 노드들만이 존재한다.

자신보다 작으면서 차이는 가장 적은 노드 값을 찾으려면 어느 노드에 방문해야 할까? 왼쪽 자식 노드로 한번 이동해서, (자신보다 작은 노드 값들 중에서) 가능한 오른쪽으로 쭉 이동하면, (그 중에서 가장 큰 노드 값으로 가면) 원하는 노드 값을 찾을 수 있다.

마찬가지로, 자신보다 크면서 차이는 가장 적은 노드 값을 찾으려면 오른쪽 자식 노드로 한번 이동 후. 가능한 왼쪽 자식 노드로 쭉 이동하면 원하는 노드 값을 찾을 수 있다.

트리의 3가지 순회 방법중, 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순으로 방문하는 중위 순회를 이용해 순회하고, 현재 노드를 순회하기 전에 방문했던 노드 값을 저장하고 있는 변수를 두면 모든 노드에서 자신보다 작거나, 크면서 차이가 가장 적은 노드 값과 자신의 노드 값과의 차를 구할 수 있고, 그 중 가장 작은 값을 정답으로 반환해주면 된다.

[10, 5, 15, 3, 7, 11, 17]을 노드 값으로 가지고 있는 이진 탐색 트리의 예시 그림이다. 중위 순회의 방문 순서를 같이 표시하였는데, 특정 노드에서 왼쪽 -> 오른쪽 쭉.... 의 노드와 오른쪽 -> 왼쪽 쭉....의 노드 방문 순서가 1씩 나므로, 현재 노드 값 - 이전 방문 노드 값을 모든 노드에서 구해주면 임의의 두 노드의 차 중 가장 작은 값을 확인할 수 있다.

소스 코드

class Solution:
    answer = sys.maxsize
    prev = -sys.maxsize
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        if root.left:
            self.minDiffInBST(root.left)
        self.answer = min(self.answer, root.val - self.prev)
        self.prev = root.val
        if root.right:
            self.minDiffInBST(root.right)
        return self.answer

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

풀이 과정

이진 탐색 트리에서 low <= node.val <= high인 노드의 합을 구하는 문제이다.

이진 탐색 트리의 특성상 어떤 노드의 왼쪽 서브 트리에는 더 작은 노드 값을 가지고 있는 노드들만, 오른쪽 서브 트리에는 더 큰 노드 값을 가지고 있는 노드들만 존재한다.

루트 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순회하는 전위 순회 방법으로 문제를 해결하였다.

현재 순회중인 노드 값이 low 보다 낮다면, 이진 탐색 트리의 특성상 왼쪽 서브 트리에 있는 노드들은 low보다 작은 값을 가질 것이므로, 순회할 필요가 없고, 현재 순회중인 노드 값이 high보다 크다면, 오른쪽 서브 트리에 있는 노드들은 high보다 큰 값을 가질 것이므로 마찬가지로 순회할 필요가 없다.

위와 같은 특성을 이용하면 풀이 시간이 줄어들지만, 그냥 모든 노드를 다 탐색해도 시간 초과가 발생하지는 않는 문제였다.

소스 코드

class Solution:
    sum = 0
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if not root:
            return None
        if low <= root.val <= high:
            self.sum += root.val
            self.rangeSumBST(root.left, low, high)
            self.rangeSumBST(root.right, low, high)
        elif root.val < low:
            self.rangeSumBST(root.right, low, high)
        elif high < root.val:
            self.rangeSumBST(root.left, low, high)
        return self.sum

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

풀이 과정

이진 탐색 트리를 Greater Sum Tree로 바꿔야 한다. Greater Sum Tree의 각 노드 값은, 기존 이진 탐색 트리에서 자신보다 큰 값을 가진 노드 값들의 합이다.

문제의 예시를 보면 파란색 글씨로 써져있는 Greater Sum Tree의 각 노드 값이, 기존 이진 탐색 트리의 각 노드에서 자신보다 더 큰 값을 가진 노드 값들의 합을 값으로 가지고 있음을 확인할 수 있다.

트리의 순회 3가지를 떠올려보자.

1. 전위 순회

루트 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리

2. 중위 순회

왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트

3. 후위 순회

왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트

이 문제는 중위 순회 과정을 살짝 바꾸어 오른쪽 서브 트리 -> 루트 -> 왼쪽 서브 트리 순으로 순회하게끔 하고 값을 누적해나가면 해결할 수 있다.

소스 코드

class Solution:
    val = 0
    def bstToGst(self, root: TreeNode) -> TreeNode:
        if root:
            self.bstToGst(root.right)
            self.val += root.val
            root.val = self.val
            self.bstToGst(root.left)
        return root

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

풀이 과정

정렬된 배열을 이진 탐색 트리로 변환하는 문제이다.

재귀를 사용해 divide-conquer 방식으로 절반씩 분할해가면서 문제를 해결하였다.

소스 코드

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        mid = len(nums) // 2
        node = TreeNode(nums[mid])
        node.left = self.sortedArrayToBST(nums[:mid])
        node.right = self.sortedArrayToBST(nums[mid+1:])
        return node

https://leetcode.com/problems/minimum-height-trees/

풀이 과정

트리간의 연결 관계가 주어지는데, 어떤 노드를 root로 삼아야 가장 높이가 낮은 트리를 구성할 수 있는지 묻는 문제이다.

남은 노드가 2개 이하가 될 때 까지, 리프 노드를 제거해가면서 문제를 해결하였다.

소스 코드

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n <= 1:
            return [0]
        
        graph = collections.defaultdict(list)
        for s, d in edges:
            graph[s].append(d)
            graph[d].append(s)
            
        leaves = []
        
        for s in graph:
            if len(graph[s]) == 1:
                leaves.append(s)
        
        while n > 2:
            n -= len(leaves)
            new_leaves = []
            for leaf in leaves:
                neigh = graph[leaf].pop()
                graph[neigh].remove(leaf)
                if len(graph[neigh]) == 1:
                    new_leaves.append(neigh)
            leaves = new_leaves
        
        return leaves

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

풀이 과정

주어진 이진 트리가 균형잡힌 이진 트리인지 확인하는 문제이다.

균형잡힌 이진 트리란, 모든 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이가 2보다 작은 이진 트리를 의미한다.

재귀를 활용해 리프 노드를 탐색하고, 리프 노드에서 현재 노드까지의 거리를 기록하게끔 코드를 작성하였다. 현재 노드에서 왼쪽 자식을 통해 탐색 가능한 리프 노드까지와의 거리와, 오른쪽 자식을 통해 탐색 가능한 리프 노드까지의 거리가 1 이상 차이가 나는 노드가 존재하면, 그 트리는 균형잡힌 이진 트리가 아니다.

소스 코드

class Solution:
    def isBalanced(self, root: Optional[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/serialize-and-deserialize-binary-tree/

풀이 과정

이진 트리를 직렬화(일자로) 했다가 다시 역직렬화 하는 문제이다.

BFS로 트리를 순회하면서, 방문 순서대로 문자열에 넣었다. 방문한 노드가 실제 존재하지 않는 노드라면, 문자열에 #을 추가하게끔 하였다. 역직렬화 과정중 문자열에서 각 노드의 값을 다시 추출하기 편하도록 문자열에서의 노드들의 값은 공백으로 구분하게끔 했다.

예시와 같은 트리를 BFS로 방문하면서 앞서 언급한대로 직렬화 한다면 serial = "1 2 3 # # 4 5"가 직렬화된 문자열로 저장될 것이다.

역직렬화 과정때도 BFS 과정을 통해 다시 트리로 바뀌게끔 구현하였다. "1 2 3 # # 4 5" 라는 문자열이 다시 위의 그림과 같이 역직렬화 되도록 구현하였다. 말로 풀어 설명하는 것보다는 코드를 읽으면 이해가 갈 것이다.

소스 코드

class Codec:

    def serialize(self, root):
        serial = ""
        Q = deque([root])
        while Q:
            cur_node = Q.popleft()
            if not cur_node:
                continue
            serial += str(cur_node.val)
            serial += ' '
            if cur_node.val == '#':
                continue
            if cur_node.left:
                Q.append(cur_node.left)
            else:
                Q.append(TreeNode('#'))
            if cur_node.right:
                Q.append(cur_node.right)
            else:
                Q.append(TreeNode('#'))
        
        while serial and serial[-1] == '#':
            serial = serial[:-1]
        
        return serial
        

    def deserialize(self, data):
        index = 0
        data = data.split()
        length = len(data)
        if length == 0:
            return None
        if data[index] != '#':
            root = TreeNode(data[index])
            index += 1
        if index >= length:
            return root
        Q = collections.deque([root])
        
        while Q:
            cur_node = Q.popleft()
            if data[index] != '#':
                cur_node.left = TreeNode(data[index])
                Q.append(cur_node.left)
            index += 1
            if index >= length:
                return root
            if data[index] != '#':
                cur_node.right = TreeNode(data[index])
                Q.append(cur_node.right)
            index += 1
            if index >= length:
                return root
        
        return root

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

풀이 과정

두 개의 이진트리의 값을 더해서 합친 이진트리를 반환하는 문제이다.

재귀를 사용해 이진 트리의 모든 노드를 순회하면서 합쳐 새로운 이진 트리를 만들어 반환하게끔 하였다.

소스 코드

# 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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 and root2:
            node = TreeNode(root1.val + root2.val)
            node.left = self.mergeTrees(root1.left, root2.left)
            node.right = self.mergeTrees(root1.right, root2.right)
            return node
        else:
            return root1 or root2

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

풀이 과정

모든 노드의 왼쪽 자식 노드와 오른쪽 자식 노드를 바꾸는 문제이다.

DFS 혹은 BFS로 트리의 노드들을 순회하면서, 왼쪽 자식노드와 오른쪽 자식노드를 변경해주면 된다.

소스 코드

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root:
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
            return root
        return 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        Q = collections.deque([root])
        while Q:
            node = Q.popleft()
            if node:
                node.left, node.right = node.right, node.left
                Q.append(node.left)
                Q.append(node.right)
        return root