0652 Find Duplicate Subtrees

0652 Find Duplicate Subtrees#

Problem#

Given the root of a binary tree, return all duplicate subtrees.

For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with the same node values.

Examples#

Example 1:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

Example 2:

Input: root = [2,1,1]
Output: [[1]]

Example 3:

Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]

Analysis#

  • leaf node是最简单的子树

  • 可以把后序遍历到的子树以serialize, 存放在hash map里面，并记录frequency

    • 问题： 为什么不能中序或者前序？

  • 输出所以frequency大于1的子树

class Node():
    def __init__(self, val=0, left=None, right=None):
        self.val = val 
        self.left = left
        self.right = right

# some helper function
def buildFromPreorderSerialization(s):
    ss = s.split(',')

    # do preorder traverse
    def traverse():

        node_val = ss.pop(0)
        if node_val == "null":
            return None
        # 
        node = Node(int(node_val))

        # traverse left
        node.left = traverse()
        # traverse right
        node.right = traverse()

        return node
    
    return traverse()

def preorder(root):
    # base case
    if not root:
        return []

    # store node 
    order = [root.val]
    # traverse the left subtree and right subtree
    order.extend(preorder(root.left))
    order.extend(preorder(root.right))
    
    # return
    return order

def findDuplicateSubtree(root):

    res = []
    hashmap = {}

    # traverse helper function
    def traverse(root):
        if not root:
            return "null"
        
        left = traverse(root.left)
        right = traverse(root.right)

        # serialize subtree in postorder:
        subtree = str(root.val) + ',' + left + ',' + right
        
        # record frequency in hashmap
        # if key not found, return 0
        freq = hashmap.get(subtree,0)

        # if duplicate, then append current root
        # why cannot we use >0 here!!!!!
        if freq == 1:
            res.append(root)
        
        # update frequency
        hashmap[subtree] = freq + 1

        # return subtree
        return subtree

    traverse(root)
    return res

# test
s = '1,2,4,null,null,null,3,2,4,null,null,null,4,null,null'
root = buildFromPreorderSerialization(s)
print(preorder(root))
res = findDuplicateSubtree(root)
res_list = []

for r in res:
    res_list.append(preorder(r))

print(res_list)

[1, 2, 4, 3, 2, 4, 4]
[[4], [2, 4]]
Contents