1. 題目

給定一棵二叉樹，返回所有重復的子樹。對于同一類的重復子樹，你只需要返回其中任意一棵的根結點即可。

兩棵樹重復是指它們具有相同的結構以及相同的結點值。

示例 1：1/ \2 3/ / \4 2 4/4 下面是兩個重復的子樹：2/4 和4 因此，你需要以列表的形式返回上述重復子樹的根結點。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-duplicate-subtrees
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. DFS解題

• 將每個節點的前序遍歷字符串，存入map的key，value存儲對應的root序列數組
• 需要注意空節點，需要返回一個任意的非空字符串區分

class Solution {unordered_map<string, vector<TreeNode*>> m; public:vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {if (root == NULL)return {};vector<TreeNode*> ans;dfs(root);for(auto it = m.begin(); it != m.end(); ++it){if(it->second.size() != 1)ans.push_back(it->second.front());}return ans;}string dfs(TreeNode* root) {if(root == NULL)return "E";string str = to_string(root->val)+dfs(root->left)+dfs(root->right);//or//string str = dfs(root->left)+dfs(root->right)+to_string(root->val);//但是中序不可以m[str].push_back(root);return str;} };

總結

以上是生活随笔為你收集整理的LeetCode 652. 寻找重复的子树（DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。