23.02.17 Today’s Leetcode

혹한기 훈련으로 인해서 못풀었던 문제들을 한번에 다 몰아서 풀었다. 내 아까운 코인들, 하지만 이럴때 쓰라고 모아둔 7000코인이라서 아낌없이 redeem으로 전환해서 풀었다.

783. Minimum Distance Between BST Nodes (easy)

# 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 minDiffInBST(self, root: Optional[TreeNode]) -> int:
        res = 10**9
        def dfs(root):
            nonlocal res
            minv, maxv = 10**9, -10**9
            if not root:
                return minv, maxv
            minv = min(minv, root.val)
            maxv = max(minv, root.val)
            if root.left:
                a, b = dfs(root.left)
                res = min(res, root.val - b)
                minv = min(minv, a)
            if root.right:
                c, d = dfs(root.right)
                res = min(res, c - root.val)
                maxv = max(maxv, d)
            return minv, maxv

        dfs(root)
        return res

Inorder Traversal 을 이용한 풀이

class Solution:
    def __init__(self):
        self.previous = None
        self.min = float('inf')
        
    def minDiffInBST(self, root: TreeNode) -> int:
        self.inOrder(root)
        return self.min
        
    def inOrder(self, root: TreeNode) -> None:
        if not root:
            return
        
        self.inOrder(root.left)
        if self.previous:
            self.min = min(self.min, root.val - self.previous.val)
        self.previous = root
        self.inOrder(root.right)

989. Add to Array-Form of Integer (easy)

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        n = ""
        for i in range(len(num)):
            n += str(num[i])
        return [int(i) for i in str(int(n) + k)]

104. Maximum Depth of Binary Tree (easy)

# 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 not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

102. Binary Tree Level Order Traversal (medium)

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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        ans = [[]]
        q, temp = [root], []
        level = 0
        while q:
            target = q.pop(0)
            if not target:
                break
            ans[level].append(target.val)
            if target.left:
                temp.append(target.left)
            if target.right:
                temp.append(target.right)
            if not q and temp:
                q = temp[:]
                temp = []
                ans.append([])
                level += 1
        return ans

101. Symmetric Tree (easy)

# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def dfs(left, right):
            if left == None and right == None:
                return False
            elif left == None:
                return True
            elif right == None:
                return True

            res = (left.val != right.val)
            res |= dfs(left.left, right.right)
            res |= dfs(left.right, right.left)
            return res

        return not dfs(root.left, root.right)