【二叉树】寻找重复的子树

0x00 题目

给定一棵二叉树 ​

​root​

​​ 返回所有 ​

​重复​

​ 的子树

对于同一类的重复子树

你只需要返回其中 ​

​任意一棵​

​ 的根结点即可

如果两棵树具有​

​相同的结构​

​ 和 ​

​相同的结点值​

​ 则它们是重复的

0x01 思路

如何判断 ​

​重复​

​​ 的子树

先不管子树，针对 ​​

​重复​

​​ 你会想到什么？

自然会想到 ​

​哈希表​

​ 具有查重的性质

怎么实现重复的 ​

​判断​

​ 呢

如何设计能够让 ​

​重复的结构​

​ 体现出来呢？

针对单个节点进行记录，无法体现出一棵 ​

​完整​

​ 的子树

那如何表示一棵 ​

​完整的​

​ 子树呢？

想想，再想想

二叉树的 ​

​序列化​

​ 问题

不就是以一个 ​

​字符串​

​ 来表示一棵完整的树么

需要对 ​

​每个节点​

​ 的子树都进行判断

所以利用 ​

​递归​

​ 来处理

使用 ​

​后序​

​ 遍历的方式

才能获取到子树的结构

0x02 解法

语言：​

​Swift​

​

树节点：​

​TreeNode​

​

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}      

func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
    // 记录出现次数
    var dic: [String:Int] = [:]
    var res: [TreeNode] = []
    
    func dfs(_ root: TreeNode?) -> String {
        guard let root = root else { return "#" }
        
        // 左子树
        let left = dfs(root.left)
        // 右子树
        let right = dfs(root.right)
        // 路径
        let path = left + "," + right + "," + "\(root.val)"
        
        // 存在
        if let count = dic[path] {
            // 增加次数
            dic[path] = count + 1
            // 之前出现过，说明是有重复的
            if count == 1 {
                res.append(root)
            }
        }else{
            dic[path] = 1
        }
        
        return path
    }
    
    _ = dfs(root)
    
    return res
}      

0x03 我的作品