652. Find Duplicate Subtrees

分手后的思念是犯贱 2024-04-03 10:36 83阅读 0赞

Given the `root` of a binary tree, return all **duplicate subtrees**.

For each kind of duplicate subtrees, you only need to return the root node of any **one** of them.

Two trees are **duplicate** if they have the **same structure** with the **same node values**.

**Example 1:**

![4f3103a48dd88d0199de0ecc0be1fd01.jpeg][]

Input: root = [1,2,3,4,null,2,4,null,null,4]
    Output: [[2,4],[4]]

**Example 2:**

![086e4e12ae97ffff55a8301fb53a8bf1.jpeg][]

Input: root = [2,1,1]
    Output: [[1]]

**Example 3:**

![b88f122d638e9360aa6852599e87a025.jpeg][]

Input: root = [2,2,2,3,null,3,null]
    Output: [[2,3],[3]]

**Constraints:**

*  The number of the nodes in the tree will be in the range `[1, 5000]`
 *  `-200 <= Node.val <= 200`

题目：给定一个二叉树，求里面完全相同的子树。返回子树根节点的集合。

思路：最暴力的办法是遍历整棵树，每遇到一个节点重新遍历树，寻找是否有与其相同的子树结构。时间复杂度是O（n^3）。因此，为简化时间复杂度，可以在遍历时将其转化成字符串数组保存起来，每次遍历到新节点只需比较是否有与其相同的字符串即可。时间复杂度简化为O(n^2)。用hashmap来保存字符串，value的值记录字符串出现的次数，只有曾经出现一次时才将子树根节点的指针保存在结果中，避免具有3个或3个以上相同子树结构时结果重复。代码：

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        string helper(TreeNode* root, unordered_map<string, int>& m, vector<TreeNode*>& res){
            if(!root){
                return "#";
            }
            string subtree = helper(root->left, m, res)+","+helper(root->right, m, res)+","+to_string(root->val);
            if(m.count(subtree) && m[subtree] == 1){
                res.push_back(root);
            }
            m[subtree]++;
            return subtree;
        }
        vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
            vector<TreeNode*> res;
            unordered_map<string, int> m;
            helper(root, m, res);
            return res;
        }
    };

[4f3103a48dd88d0199de0ecc0be1fd01.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/d63e70cb41b54a48b9c653f6277a5a21.jpeg
[086e4e12ae97ffff55a8301fb53a8bf1.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/3219821454eb40e8b648e21bd9fa6071.jpeg
[b88f122d638e9360aa6852599e87a025.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/c5593cedb4df41598acd124d35b7d672.jpeg