greentea31's Note

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

https://leetcode.com/problems/longest-univalue-path/

풀이 과정

트리에서 같은 숫자로 이루어져 있는 가장 긴 경로를 구하는 문제이다.

DFS로 리프 노드에서부터 체크하면서 부모 노드의 값이 왼쪽 자식 노드의 값과 같으면 left 변수를 증가, 오른쪽 자식 노드의 값과 같으면 right 변수를 증가시키면서 정답을 구해주면 된다.

소스 코드

# 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:
    result = 0
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            
            if node.left and node.left.val == node.val:
                left += 1
            else:
                left = 0
            if node.right and node.right.val == node.val:
                right += 1
            else:
                right = 0
            
            self.result = max(self.result, left + right)
            return max(left, right)
            
            
        dfs(root)
        return self.result



https://leetcode.com/problems/diameter-of-binary-tree/

풀이 과정

이진 트리의 지름, 즉 이진 트리의 노드들 사이의 가장 긴 경로를 구하는 문제이다.

이진 트리의 지름은 루트 노드와 리프 노드 사이의 거리이거나, 리프 노드와 리프 노드 사이의 거리이다. 루프 노트와 리프 노드의 사이의 거리는 트리의 높이를 구하면 해결할 수 있는 문제이지만 리프 노드와 리프 노드 사이의 거리는 어떻게 문제를 해결할 것인가?

DFS로 각 노드들에 리프노드와의 거리를 상태값으로 부여하자. 그러면 특정 노드를 루트로 하는 트리의 Diameter는 왼쪽 노드의 상태값 + 오른쪽 노드의 상태값 + 2가 된다.

이 모든 과정을 마쳤을 때, 루트 노드에 대해서 왼쪽 노드의 상태값 + 오른쪽 노드의 상태값 + 2를 더해주면 전체 트리의 지름을 구할 수 있다. 

자식 노드가 없는 경우에는 그 자식 노드의 상태값을 -1로 가정하고 계산을 진행해주어야 트리의 지름을 정상적으로 구할 수 있다.

소스 코드

# 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:
    longest = 0
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return -1
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            self.longest = max(self.longest, left + right + 2)
            return max(left, right) + 1
        
        
        dfs(root)
        return self.longest

https://leetcode.com/problems/maximum-depth-of-binary-tree/

풀이 과정

이진 트리의 최대 깊이를 구하는 문제이다.

트리도 (사이클이 없는) 그래프이므로 BFS, 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        
        Q = collections.deque([root])
        depth = 0
        
        while Q:
            depth += 1
            for _ in range(len(Q)):
                cur_root = Q.popleft()
                if cur_root.left:
                    Q.append(cur_root.left)
                if cur_root.right:
                    Q.append(cur_root.right)
        
        return depth