geonyeongkim

이번 문제는 인자로 binary tree와 int형 sum 값이 주어지며,

트리의 최상단에서 마지막 노드까지의 val을 sumation한 값이 인자로 주어진 sum값과 같은 경우가 있는지 판단하는 문제입니다.

저의 경우 leaf 노드를 만날때까지 탐색을 하였고, 리프노드에 도달했을때 값을 비교하여 boolean 값을 반환하도록 하였습니다.

값이 같다면 True를 반환시켰고, or 연산으로 왼쪽-오른쪽 노드 탐색을 묶어서 하나라도 sum이 같은 길을 찾으면 True로 반환되도록 하였습니다.

아래는 코드입니다.

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

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:

        if not root: return False
        res = self.findTree(root, sum, 0)
        return res

    def findTree(self, root: TreeNode, sum:int, additional_sum: int):
        if root: additional_sum += root.val
        if not root: return 
        if root.left == None and root.right == None:
            if sum == additional_sum: return True
            else: return False
        return self.findTree(root.right, sum, additional_sum) or self.findTree(root.left, sum, additional_sum)

이번 문제는 binary tree를 인자로 받아 leaf node까지의 depth 중 최소를 찾는 문제입니다.

여기서 leaf node는 왼쪽, 오른쪽 노드가 없는 것을 의미합니다.

저의 경우에는 재귀를 통해 leaf node를 발견할때까지 tree를 모두 순회하도록 하였습니다.

leaf node를 발견하면 leaf node의 depth를 반환하게 하여, 최소값을 구하도록 하였습니다.

아래는 코드입니다.

import sys

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

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: return 0
        if not root.left and not root.right: return 1
        depth = sys.maxsize

        depth = min(self.findDepth(root.right, 1), self.findDepth(root.left, 1)) + 1
        return depth

    def findDepth(self, root: TreeNode, depth: int):
        if not root: return sys.maxsize
        if not root.left and not root.right: return depth
        return min(self.findDepth(root.left, depth +1), self.findDepth(root.right, depth + 1))

이번 문제는 주어진 트리가 높이 균형 트리인지 판단하는 문제입니다.

왼쪽 노드와 오른쪽 노드의 depth 차이가 1이하여야만 합니다.

풀이로는 재귀를 통해 각 노드를 순회하면서 depth를 아래부터 1씩 증가시키면서 매깁니다.

depth를 매기면서 각 왼쪽과 오른쪽의 depth를 비교하여 1보다 크면 불균형으로 판단하도록 하였습니다.

풀이는 아래와 같습니다.

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

class Solution:

    def isBalanced(self, root: TreeNode) -> bool:
        if not root: return True

        res = self.searchDepth(root)
        if res == -1: return False
        return True

    def searchDepth(self, root: TreeNode):
        if root == None: return 0

        right_depth = self.searchDepth(root.right)
        if right_depth == -1 : return -1
        
        left_depth = self.searchDepth(root.left)
        if left_depth == -1: return -1
        
        if abs(right_depth - left_depth) > 1: return -1
        
        return max(right_depth, left_depth) + 1

이번 문제는 정렬된 List<int>를 인자로 받아 높이가 균등한 balanced binary search tree를 만드는 문제입니다.

트리의 사용 이유중에는 정렬을 위해서도 있지만, 문제에서는 이미 정렬된 문자열을 주기 때문에

문자열의 중간값을 찾고 중간에서부터 각 왼쪽과 오른쪽값들은 현재 노드에서 왼쪽과 오른쪽으로 넘겨주면 자연스럽게

높이가 균등한 BST가 완성되게 됩니다.

코드는 아래와 같습니다.

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

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums: return None

        mid = len(nums) // 2

        res = TreeNode(nums[mid])
        res.left = self.sortedArrayToBST(nums[:mid])
        res.right = self.sortedArrayToBST(nums[mid+1:])
        return res

감사합니다.

이번 문제는 주어진 트리의 각 depth 별로 수를 수집하여 List<List> 형식으로 반환해야합니다.

반환 값은 left -> right 로 숫자가 있어야 하며, 맨 아래 depth 의 값부터 들어있어야합니다.

저는 depth 값을 같이 넘겨주며, 트리를 모두 탐색하도록 하였습니다.

그리고, 마지막으로는 완성된 List를 reverse하도록 했습니다.

코드는 아래와 같습니다.

from typing import List


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

class Solution:

    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if root == None: return []
        if root.right == None and root.left == None: return [[root.val]]

        res = [[root.val]]
        depth = 0
        self.find(root.left, depth + 1, res)
        self.find(root.right, depth + 1, res)
        res.reverse()
        return res

    def find(self, root: TreeNode, depth: int, res: List[List[int]]):
        if root == None: return
        if root != None:
            if len(res) <= depth:
                res.insert(depth, [root.val])
            else:
                res[depth].append(root.val)

        self.find(root.left, depth + 1, res)
        self.find(root.right, depth + 1, res)

감사합니다.

이번 문제는 주어진 트리의 max depth를 찾는 문제입니다.

완전탐색을 통해 트리의 모든 노드를 들리며 depth의 max를 구했습니다.

코드는 아래와 같습니다.

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

class Solution:
    def maxDepth(self, root: TreeNode) -> int:

        if root == None: return 0
        if root.right == None and root.left == None: return 1
        depth = 1
        depth = max(self.find(root.right, depth), self.find(root.left, depth))
        return depth

    def find(self, root: TreeNode, depth: int):
        if root == None: return depth
        return max(self.find(root.right, depth+1), self.find(root.left, depth+1))

감사합니다.

이번 문제는 1개의 tree를 인자로 받아 대칭인지 판단하는 문제입니다.

대칭트리의 경우에는, 트리의 왼쪽부분은 왼쪽 우선으로, 오른쪽 부분은 오른쪽 우선으로 탐색 시 만나는 값의 순서가 같습니다.

그렇기 때문에, 저는 아래와 같이 풀이했습니다.

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

class Solution:

    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None: return True
        left_list = [root.val]
        right_list = [root.val]

        self.searchPriorLeft(root.left, left_list)
        self.searchPriorRight(root.right, right_list)
        
        if len(right_list) != len(left_list): return False

        for i in range(len(right_list)):
            if right_list[i] != left_list[i]: return False
        return True

    def searchPriorLeft(self, root: TreeNode, list):
        if root == None:
            list.append(None)
            return True
        list.append(root.val)
        if root.left == None and root.right == None: return True
        self.searchPriorLeft(root.left, list)
        self.searchPriorLeft(root.right, list)

    def searchPriorRight(self, root: TreeNode, list):
        if root == None:
            list.append(None)
            return True
        list.append(root.val)
        if root.left == None and root.right == None: return True
        self.searchPriorRight(root.right, list)
        self.searchPriorRight(root.left, list)

감사합니다.

이번 문제는 2개의 tree를 인자로 받아 같은지 체크하는 문제입니다.

Tree의 경우 문제에서 아래와 같은 클래스로 정의하고 있습니다.

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

저의 경우에는 아래와 같은 로직을 재귀를 통해 완전 탐색하도록 하여 문제를 풀었습니다.

0. 2개의 현재 focus되고 있는 노드 객체가 맞는지 체크

1. 현재 값이 같은지 체크

2. 왼쪽 노드 체크

3. 오른쪽 노드 체크

코드는 아래와 같습니다.

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

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p == q == None: return True
        elif p == None or q == None: return False
        return (p.val == q.val and self.isSameLeftRight(p.left, q.left) and self.isSameLeftRight(p.right, q.right))

    def isSameLeftRight(self, p: TreeNode, q: TreeNode):
        if p == q == None: return True
        elif p == None or q == None: return False
        else: return (p.val == q.val and self.isSameLeftRight(p.left, q.left) and self.isSameLeftRight(p.right, q.right))

감사합니다.

인자로 받은 문자열 중 나란히 있는 중복문자를 반복적으로 제거하고, 남은 문자열을 반환하는 문제입니다.

위 예제를 보면 아래와 같이 처리가 흐르게 됩니다.

1. abbaca -> bb 제거

2. aaca -> aa 제거

3. ca 반환

저는 아래와 같이 풀이하였습니다.

class Solution:
    def removeDuplicates(self, S: str) -> str:
        stack = []
        stack.append(S[0])

        for i in S[1:]:
            if stack and stack[-1] == i:
                stack.pop()
            else:
                stack.append(i)
        return ''.join(stack)

stack으로 이용할 list를 하나 만들었습니다.

그 후, 문자열을 iterate하며 stack에서 peek한 결과와 동일하면 pop 아니면 append 하였습니다.

감사합니다.

이번 문제는 간단히 Stack의 기능인 push, pop, top에서 추가로 getMin 함수를 구현하는 클래스를 작성하면 됩니다.

저는 아래와 같이 풀었습니다.

class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return min(self.stack)

감사합니다.