种星星
0%

LeetCode题解|652. Find Duplicate Subtrees

发表于 阅读次数： Valine：

题目链接：652. Find Duplicate Subtrees

概述

本题给定一棵二叉树，要求找出所有的重复子树。

思路

对这棵树进行前序遍历，如果某一子树的前序遍历序列已经出现过，说明这棵子树是重复出现的，将其加入结果集即可。

实现

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
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode[]}
 */
var findDuplicateSubtrees = function(root) {
    let map = {};
    let result = [];

    let preorder = (node) => {
        if(node == null){
            return "#";
        }
        let vs = preorder(node.left) + preorder(node.right) + node.val;
        if(map[vs]){
            if(map[vs] == 1){
                result.push(node);
            }
            map[vs] += 1;
        }
        else{
            map[vs] = 1;
        }
        return vs;
    }
    preorder(root);
    return result;
};

题解合集