652.Find Duplicate Subtrees

tags: Medium,DFS,Binary Tree,Tree,Hash Table

652. Find Duplicate Subtrees

題目描述

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:

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

Example 2:

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

Example 3:

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

解答

C++

class Solution {
public:
    unordered_map<string, int> count;
    vector<TreeNode*> ans;

    string encode(TreeNode* node) {
        if (!node) return "";
        string key = to_string(node->val) + ","
                     + encode(node->left) + ","
                     + encode(node->right);
        if (count[key]++ == 1) ans.push_back(node);
        return key;
    }

    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        encode(root);
        return ans;
    }
};

Yen-Chi ChenTue, Feb 28, 2023

Python

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        ans = []
        counter = defaultdict(int)

        def encode(node):
            if not node: return ''
            key = str(node.val) + ',' \
                  + encode(node.left) + ',' \
                  + encode(node.right)
            counter[key] += 1
            if counter[key] == 2:
                ans.append(node)
            return key
        
        encode(root)
        return ans

Yen-Chi ChenTue, Feb 28, 2023

Time:

$O(n)$
Extra Space:

$O(n^2)$ 儲存每顆樹的序列string

XD Feb 28, 2023

Reference

回到題目列表