652. Find Duplicate Subtrees 寻找重复的子树

题目地址：https://leetcode.com/problems/find-duplicate-subtrees/description/

题目描述：

Given 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.

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

Example 1:

    1
   / \
  2   3
 /   / \
4   2   4
   /
  4

Thefollowing are two duplicate subtrees:

  2
 /
4

and

4

Therefore, you need to return above trees' root in the form of a list.

题目大意

找出一个二叉树中所有的重复子树。重复子树就是一棵子树，在大的二叉树中出现的次数不止一次。

解题方法

暴力解法不可取。

参考了[LeetCode] Find Duplicate Subtrees 寻找重复树open in new window才明白，我们要找到一个重复的子树，可以把树和hash结合起来啊！

每一棵子树，都能把它的结构使用先序遍历或者后序遍历保存下来，然后把这个结构保存在hash表格里面，这样当我们下次再遇到这个树的结构的时候，就能很容易查表得知，然后放到结果res中。

代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findDuplicateSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: List[TreeNode]
        """
        res = []
        m = collections.defaultdict(int)
        self.helper(root, m, res)
        return res
        
    def helper(self, root, m, res):
        if not root:
            return '#'
        path = str(root.val) + ',' + self.helper(root.left, m, res) + ',' + self.helper(root.right, m, res)
        if m[path] == 1:
            res.append(root) 
        m[path] += 1
        return path

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发