leetcode 24(구현, linked_list), 572(트리), 508(트리)

24 https://leetcode.com/problems/swap-nodes-in-pairs/

 

가져와서 구현해준다. https://leetcode.com/problems/swap-nodes-in-pairs/discuss/œ/Python-or-Dummynode에 좋은 풀이가 있다. 내 답은 드러워서 안적음

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = p = ListNode(0)
        dummy.next = head
        while head and head.next:
            tmp = head.next
            head.next = tmp.next
            tmp.next = head
            p.next = tmp
            head = head.next
            p = tmp.next
        return dummy.next

572 https://leetcode.com/problems/subtree-of-another-tree/

 

트리를 문자열로 만든다음에 서브트리에 속하는지 본다. 이해가 안되었던 예시가 [1,2,3], [1,2]는 False가 나와야하는데 이유는 동일한 루트 1이지만 서브트리에는 오른쪽자식인 3이 없기 때문이다.

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        self.s1, self.s2 = '', ''
        def inorder(node, f):
            if not node:
                if f: self.s1 += '#'
                else: self.s2 += '#'
                return
            inorder(node.left, f)
            if f: self.s1 += str(node.val)
            else: self.s2 += str(node.val)
            inorder(node.right, f)
            if f:  self.s1 += '$'
            else:  self.s2 += '$'
        inorder(root, True)
        inorder(subRoot, False)
        return self.s2 in self.s1

근데 답중에 깔끔하게 구현한 답이 있음.

https://leetcode.com/problems/subtree-of-another-tree/discuss/265239/Python-Easy-to-Understand

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s: 
            return False
        if self.isSameTree(s, t): 
            return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        return p is q

508 https://leetcode.com/problems/most-frequent-subtree-sum/

 

재귀적으로 탐색하면서 푼다. 문제특성상(?) 재귀적으로 푸는게 맞는것 같다.

class Solution:
    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
        s = {}
        def dfs(node):
            if not node:
                return 0
            l = dfs(node.left)
            r = dfs(node.right)
            s[l + r + node.val] = s.get(l + r + node.val, 0) + 1
            return l + r + node.val   
        dfs(root)
        max_count = max(s.values())
        return [k for k,v in s.items() if v == max_count]