leetcode 297(트리), 449, 606(트리), 652(트리)

297 https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

449 https://leetcode.com/problems/serialize-and-deserialize-bst/

똑같은 문제라서 같이 올림. 문자열로 인코딩하고 디코딩해주는 문제이다. 

from collections import deque
class Codec:

    def serialize(self, root):
        if not root:
            return ''
        ret = deque()
        queue = deque([root])
        while queue:
            p = queue.popleft()
            if not p:
                ret.append('null')
                continue
            ret.append(p.val)
            for child in [p.left, p.right]:
                queue.append(child)
        return ','.join(map(str, ret))

    def deserialize(self, data):
        if data == '':
            return 
        data = deque(data.split(','))
        root = TreeNode(data.popleft())
        queue = deque([root])
        while queue and data:
            node = queue.popleft()
            if data:
                p = data.popleft()
                if p != 'null':
                    node.left = TreeNode(int(p))
                    queue.append(node.left)
            if data:
                p = data.popleft()
                if p != 'null':
                    node.right = TreeNode(int(p))
                    queue.append(node.right)
        return root

606 https://leetcode.com/problems/construct-string-from-binary-tree/

recursive하게 순회하면서 푼다.

class Solution(object):
    ret = ''
    def tree2str(self, t):
        def pre(node):
            if not node:
                return
            if not (node.left or node.right):
                self.ret += str(node.val)
            else:
                self.ret += str(node.val)
                if node.left or node.right:
                    self.ret += '('
                    pre(node.left)
                    self.ret += ')'
                if node.right:
                    self.ret += '('
                    pre(node.right)
                    self.ret += ')'
                
        pre(t)
        return self.ret

652 https://leetcode.com/problems/find-duplicate-subtrees/

처음에 어떻게해야할지 아이디어가 안 떠올라서 discussion을 참조했다. 

https://leetcode.com/problems/find-duplicate-subtrees/discuss/106030/Python-O(N)-Merkle-Hashing-Approach 글을 보면 같은 트리인지 판별하는 방식으로는 아래 트리의 값을들 hash한 후 그것을 키로 딕셔너리에 저장해둔다. 하나의 키에 동일한 값이 여러개 있으면 그게 중복되는 서브트리가 있다는 증거로 사용된다.

근데 트리의 value가 모두 숫자이므로 굳이 해시를 쓸 필요도 없이 !value!같은거로 인코딩 해주고 이걸 키로 써서 풀었다. 

from collections import defaultdict
class Solution(object):
    def findDuplicateSubtrees(self, root):
        def pre(node):
            if not node:
                return '#'
            left = pre(node.left)
            right = pre(node.right)
            tree_val = '!{}!'.format(left + str(node.val) + right)
            found_dict[tree_val].append(node)
            return tree_val

        found_dict = defaultdict(list)
        pre(root)
        return [v[0] for v in found_dict.values() if len(v) > 1]

value가 숫자가 아니라 모든 문자를 포함하는 경우이면 해시같은걸 써야하는데, 해시는 또 해시 콜리전 문제가 있다. 그것에 대해서는 요 글을 또 읽어보자. 

다른 내용도 있지만 내가 얻은것만 요약하면 tuple이나 frozenset을 써서 해시함수처럼 사용할수 있다고 한다. 근데 tuple은 tuple자체의 값을 해싱해서 갖고있지 않아서 튜플을 만들때마다 계속 물어봐서 frozenset이 더 빠르다고 한다..