[Mock] Microsoft 6

669. Trim a Binary Search Tree

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

My Answer 1: Wrong Answer (27 / 78 test cases passed.)

# 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 trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        # 어려워보여요...
        
        result = TreeNode(0)
        prev = None
        head = root
        
        # low ~ high 범위에 드는 값으로 맨 처음 root 잡아주기
        while root:
            if low <= root.val <= high:
                break
            elif root.val < low:
                root = root.right
                head = root
            elif root.val > high:
                root = root.left
                head = root
        
        # trim 쇼~
        while root:
            if root.val == low:
                root.left = None
                prev = root
                root = root.right
            
            elif root.val == high:
                root.right = None
                prev = root
                root = root.left
            
            elif low < root.val < high:
                if root.right:
                    root = root.right
                elif root.left:
                    root = root.left
                else:
                    break
                
            elif root.val > high:
                # 무조건 왼쪽에
                prev.right = root.left
                root = root.left
            
            elif root.val < low:
                # 무조건 오른쪽에
                if prev:
                    prev.left = root.right
                root = root.right
        
        return head

허접코드 탄생~~~!!!

left, right 중에 아닌 값들은 사정없이 None 으로 싹둑 잘라버리자 했는데...

그 속에 숨겨진 알맹이를 못봤네요..^^

진짜를 보려면 재귀가 답인듯~~

Solution 1: Accepted (Runtime: 48 ms - 86.82% / Memory Usage: 18.2 MB - 59.94%)

# 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 trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        def trim(node):
            if not node:
                return None
            elif node.val > high:
                return trim(node.left)
            elif node.val < low:
                return trim(node.right)
            else:
                node.left = trim(node.left)
                node.right = trim(node.right)
                return node

        return trim(root)

재귀로 알맹이들을 찾아주네요^^

val 가 low ~ high 사이면 left, right 양쪽의 알맹이 찾으러 각각 재귀 돌려줌

val 가 high 보다 크면 left 알맹이만 , low 보다 작으면 right 알맹이만 찾기

---

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

My Answer 1: Accepted (Runtime: 72 ms - 50.25% / Memory Usage: 14.4 MB - 43.90%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        tmp = 1
        a = 0
        while l1:
            a += l1.val*tmp
            l1 = l1.next
            tmp *= 10
        
        tmp = 1
        b = 0
        while l2:
            b += l2.val*tmp
            l2 = l2.next
            tmp *= 10
        
        twosum = a + b
        
        result = ListNode(0)
        head = result
        
        #while twosum:
        for _ in range(len(str(twosum))):
            result.next = ListNode(twosum % 10)
            twosum //= 10
            result = result.next
        
        return head.next

원래 이문제는 아니었지만...^^

얜 뭔가 넘 자주 봐서 익숙하네요