Find duplicate subtree

One quick approach to handle subtree issue:

class Solution(object):
    def findDuplicateSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: List[TreeNode]
        """


        def put_map(node,m,res):
            if not node:
                return 'None'
            l = put_map(node.left, m, res)
            r = put_map(node.right, m, res)
            k = (node.val, l, r)   <------ this is the key, it only saves node value and left/right node
            if k not in m:
                m[k] = node
            else:
                res.add(m[k])
            return m[k]

        res = set()
        m = dict()
        put_map(root, m, res)
        return list(res)

Subtree of another tree

use the same approach!

class Solution(object):
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """

        cache = {}
        def dfs(root):
            if not root: 
                return None

            left = dfs(root.left)
            right = dfs(root.right)

            if left == t or right == t: 
                return t

            if (root.val, left, right) in cache: 
                return cache[(root.val, left, right)]
            else:
                cache[(root.val, left, right)] = root
                return root

        dfs(t)
        return dfs(s) == t