UNIST, CSE 3th

3 minute read

35. Search Insert Position (easy)

Binary Search

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        start, end = 0, len(nums)
        while start < end:
            mid = (start + end) // 2
            temp = nums[mid]
            if temp == target:
                return mid
            elif temp < target:
                start = mid + 1
            elif temp > target:
                end = mid
        return start

653. Two Sum IV - Input is a BST (easy)

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        db = set()
        def dfs(node):
            if not node:
                return False
            target = k - node.val
            if target in db:
                return True
            db.add(node.val)
            res = False
            res |= dfs(node.left)
            res |= dfs(node.right)
            return res
        
        return dfs(root)

235. Lowest Common Ancestor of a Binary Search Tree (medium)

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        road = set()
        ans = root
        temp = root
        while temp != p:
            if temp.val < p.val:
                temp = temp.right
            else:
                temp = temp.left
            road.add(temp)
        
        temp = root
        while temp != q:
            if temp.val < q.val:
                temp = temp.right
            else:
                temp = temp.left
            if temp in road:
                ans = temp
        return ans

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root.val == p.val || root.val == q.val) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        if (left != null) return left;
        return right;
    }
}

BST의 특징을 이용하자.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)

        else:
            return root

99. Recover Binary Search Tree (medium)

단 한번의 swap으로 Binary Tree를 정상적으로 만들어야 하는 문제. 처음 구현한 방식은 다음과 같다. 값이 이상한 두 node를 구하는게 가장 큰 문제였고, 그 문제는 이미 풀어보았기 때문에 같은 방식으로 help 함수를 구현했다. 그리고 한번의 help 함수를 호출하고 찾은 두 node의 값을 swap하면 끝날 줄 알았지만.. 그렇게 간단하지 않았다.

counter example이 있더라… 그래서 단순히 여러번 찾아서 바꾸는 방식으로 구현해보니 testcase를 통과하긴 했다. 하지만 불보듯이 뻔하지만 결과는 처참했다.

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        
        def help(node, left, right):
            if node.val <= left.val:
                return left, node
            if node.val >= right.val:
                return node, right
            a, b = None, None
            if node.left:
                temp = node if node.val < right.val else right
                if not a or not b:
                    a, b = help(node.left, left, temp)
            if node.right:
                temp = node if node.val > left.val else left
                if not a or not b:
                    a, b = help(node.right, temp, right)
            return a, b
        
        m, n = TreeNode(-math.inf), TreeNode(math.inf)
        a, b = help(root, m, n)
        while a and b:
            a, b = help(root, m, n)
            if not a or not b:
                break
            a.val, b.val = b.val, a.val
        return root

다른 방법을 생각해내야 했다. BST라는 가장 큰 특징을 살리지 못했다. 아래는 BST의 값을 inorder traversal를 이용하여 값을 뽑아내고 이를 이용하여 푸는 정말 멋진 솔루션이다.

# 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:
    odr = []
    val = []

    def recursion(self, root):
        if root==None:
            return
        self.recursion(root.left)
        self.odr.append(root)
        self.val.append(root.val)
        self.recursion(root.right)
        return

    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.odr = []
        self.val = []
        self.recursion(root)
        sortval = sorted(self.val)
        index = []
        for i in range(len(self.val)):
            if self.val[i] != sortval[i]:
                index.append(i)

        self.odr[index[0]].val, self.odr[index[1]].val = self.odr[index[1]].val, self.odr[index[0]].val

You may also enjoy