[leetcode] 652. Find Duplicate Subtrees

[leetcode] 652. Find Duplicate Subtrees

Description

Given 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 same node values.

Example 1:

1 / \ 2 3 / / \ 4 2 4 / 4

The following are two duplicate subtrees:

2 / 4

and

4

Therefore, you need to return above trees’ root in the form of a list.

分析

题目的意思是：找出一个二叉树的重复子树。

用到了后序遍历，还有数组序列化，并且建立序列化跟其出现次数的映射，这样如果我们得到某个结点的序列化字符串，而该字符串正好出现的次数为1，说明之前已经有一个重复树了，我们将当前结点存入结果res，这样保证了多个重复树只会存入一个结点。

代码

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

参考文献

​​[LeetCode] Find Duplicate Subtrees 寻找重复树​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。