（js）leetcode 652. 寻找重复的子树

雨点打透心脏的1/2处 2022-11-06 08:56 140阅读 0赞

### 题目： ###

> 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
> 
> 两棵树重复是指它们具有相同的结构以及相同的结点值。
> 
> 示例 1：
> 
>         1  
>        / \\  
>       2   3  
>      /   / \\  
>     4   2   4  
>        /  
>       4  
> 下面是两个重复的子树：
> 
>       2  
>      /  
>     4  
> 和
> 
>     4  
> 因此，你需要以列表的形式返回上述重复子树的根结点。

### 思路： ###

> 使用后序遍历
> 
> 通过拼接字符串的方式把二叉树序列化，左右子树加上自己，就是以自己为根的二叉树序列化结果

### 代码实现： ###

/**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {TreeNode[]}
     */
    var findDuplicateSubtrees = function (root) {
        let memo = new Map();
        let res = [];
    
        var traverse = function (root) {
            if (root == null) {
                return '#';
            }
            let left = traverse(root.left);
            let right = traverse(root.right); 
    
            let subTree = left + ',' + right + ',' + root.val;
            let count = memo.get(subTree) || 0;
            if (count === 1) {
                res.push(root)
            }
            // 给子树对应的出现次数加1
            memo.set(subTree, ++count)
            return subTree
        }
        traverse(root);
        return res;
    };

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70]: /images/20221023/410f16a50f024043b58a1dae6511f646.png