23.02.28 Today’s Leetcode

652. Find Duplicate Subtrees (medium)

DFS approach

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        if not root:
            return []

        def isDiff(node1, node2):
            if node1 and node2:
                res = (node1.val != node2.val)
                res |= isDiff(node1.left, node2.left)
                res |= isDiff(node1.right, node2.right)
                return res
            if not node1 and not node2:
                return False
            return True

        def height(node):
            if not node:
                return 0
            return 1 + max(height(node.left), height(node.right))
        
        ans = []
        def dfs(node1, node2):
            nonlocal ans
            if not node1 and not node2:
                return
            res = isDiff(node1, node2)
            h1, h2 = height(node1), height(node2)
            if node1 and node2:
                print(node1.val, node2.val, res)
            if h1 < h2 :
                dfs(node1, node2.left)
                dfs(node1, node2.right)
            if h1 > h2:
                dfs(node1.left, node2)
                dfs(node1.right, node2)
            if h1 == h2:
                if not res:
                    if node1 not in ans:
                        ans.append(node1)
                if node1 and node2:
                    dfs(node1.left, node2.left)
                    dfs(node1.left, node2.right)
                    dfs(node1.right, node2.left)
                    dfs(node1.right, node2.right)

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

subtree에 ID를 부여해서 문제를 풀어가는 아이디어가 돋보인다. 내가 문제를 풀 때 고민이었던 duplicated node를 제거할 필요없이 ID를 이용해서 distinct하게 node를 선택할 수 있다는 점이 신기하다.

class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        def traverse(node):
            if not node:
                return None
            left = traverse(node.left)
            right = traverse(node.right)

            subtree = (node.val, left, right)
            subtree_id = subtree_ids.get(subtree)
            if subtree_id is None:
                subtree_id = len(subtrees)
                subtrees.append(subtree)
                subtree_ids[subtree] = subtree_id
            subtree_counts[subtree_id] += 1
            if subtree_counts[subtree_id] == 2:
                duplicates.append(node)
            return subtree_id

        subtrees = []
        subtree_ids = {}
        subtree_counts = defaultdict(int)
        duplicates = []
        traverse(root)
        return duplicates

617. Merge Two Binary Trees (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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node1, node2):
            node1.val += node2.val
            if node1.left and node2.left:
                dfs(node1.left, node2.left)
            if node1.right and node2.right:
                dfs(node1.right, node2.right)
            if not node1.left and node2.left:
                node1.left = TreeNode(0)
                dfs(node1.left, node2.left)
            if not node1.right and node2.right:
                node1.right = TreeNode(0)
                dfs(node1.right, node2.right)
        
        if root1 and root2:
            dfs(root1, root2)
        if root1:
            return root1
        return root2

166. Fraction to Recurring Decimal (medium)

순환소수를 표현하는 방식 - 어떻게 구현할지 잘 보여주는 문제.

class Solution:
    def fractionToDecimal(self, nu: int, de: int) -> str:
        cf = ""
        if nu * de < 0:
            cf = "-"
        nu = abs(nu)
        de = abs(de)
        st1 = nu // de
        re = abs(nu % de)
        st1 = str(st1)
        st2 = ""
        # print(st1)
        i = 0
        dc = {}
        while re > 0:
            if re < de:
                re *= 10
            if (re, de) in dc:
                st2 = st2[:dc[(re,de)]] + "(" + st2[dc[(re, de)]:] + ")"
                break
            dc[(re, de)] = i
            i += 1
            st2 += str(re // de)
            re = re % de
        if st2 == "":
            return cf + st1
        return cf + st1 + "." + st2