LeetCode 652 Find Duplicate Subtrees

Tag: 二叉树 LeetCode Posted on 2022-02-06 22:52:42 Edited on 2022-02-06 22:59:13 Views: 155

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/