652.寻找重复的子树

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

一、递归遍历

在树中找结构相同的子树，一定是先子节点再根节点，即后序遍历。

写出框架

def travel(root):
	if root空: return
	left = travel(root.left)
	right travel(root.right)
	得到序列，判断

得到遍历序列后再比较，经过尝试发现前序后序均可，唯独中序不行。注意前序定义是根、左、右，其实根、右、左在逻辑上和前序是等价的。后序亦然

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        self.hash = {}	#存储重复序列
        self.res = []	 #结果
        def traval(root):
            if not root:
                return 'null'
            left = traval(root.left)
            right = traval(root.right)
            # 以下几种顺序均可
            s =  str(root.val) + ',' + str(left) + ',' + str(right)  #前序
            # s =  str(root.val) + ',' + str(right) + ',' + str(left)  #还是前序
            # s =  str(right)+ ',' + str(left) + ',' + str(root.val) 	#后序
            # s =  str(left)+ ',' + str(right) + ',' + str(root.val)   	#也是后序
            # 统计出现次数
            self.hash[s] = self.hash.get(s, 0) + 1	
            if self.hash[s] == 2:
                self.res.append(root)		#遇到重复的序列，把根（而不是序列）加入结果
            return s	#记得返回序列
        
        traval(root)
        return self.res