LeetCode 652 Find Duplicate Subtrees

    
        标签：
        
            二叉树
        
            LeetCode
        
    发布于：2022-02-06 22:52:42
    编辑于：2022-02-06 22:59:13
    浏览量：1131

概述

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

递归法

拿到题目的第一反应，是将树转化为成等价字符串。

之后构造一个 map，key 为字符串，value 即 count 及对应的根节点。

class Solution {
public:
    map<string, int> countMap;
    map<string, TreeNode*> rootMap;
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        hashTree(root);
        vector<TreeNode*> ans;
        for (auto const& x : countMap) {
            if (x.second > 1) {
                ans.push_back(rootMap[x.first]);
            }
        }
        return ans;
    }
    
    string hashTree(TreeNode* root) {
        if (!root) return "";
        string hash = to_string(root->val) + "(" + hashTree(root->left) + "," + hashTree(root->right) + ")";
        countMap[hash]++;
        if (countMap[hash] == 1) rootMap[hash] = root;
        return hash;
    }
};

实际上没有必要专门搞一个 rootMap，当 count 为 2 的时候直接放到结果列表里即可。

class Solution {
public:
    map<string, int> countMap;
    vector<TreeNode*> ans;
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        hashTree(root);
        return ans;
    }
    
    string hashTree(TreeNode* root) {
        if (!root) return "";
        string hash = to_string(root->val) + "(" + hashTree(root->left) + "," + hashTree(root->right) + ")";
        countMap[hash]++;
        if (countMap[hash] == 2) ans.push_back(root);
        return hash;
    }
};

Links: leetcode-652-find-duplicate-subtrees