- 已关闭。**此问题需要debugging details。当前不接受答案。
编辑问题以包含desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem。这将有助于其他人回答问题。
4天前关闭。
Improve this question
问题是找到重复的子树,使用的方法是将每个子树转换为后序树并比较它们。
class Solution {
public:
vector<TreeNode*> ans;
unordered_map<string, int> list;
string helper(TreeNode* root){
if(!root)return "";
string cur = helper(root->left)+" "+helper(root->right)+" "+to_string(root->val);
if(list[cur] == 1)ans.push_back(root);
list[cur]++;
return cur;
}
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
helper(root);
return ans;
}
};
但是当我用中阶遍历来尝试同样的问题时,它不起作用,有人能解释一下为什么吗?
我想知道为什么它不适用于中序遍历,而只适用于前序和后序字符串。
1条答案
按热度按时间xwbd5t1u1#
考虑下面两棵树:
两棵树的中序遍历都是
1 -> 2 -> 3
,简单地说,中序遍历不能保证唯一性,这就是为什么你的解决方案会返回一个不正确的答案。使用前序/后序遍历也不能保证唯一性,如果你在遍历中包含“null”节点,那么它们会给予每棵树一个唯一的字符串,但即使这样,中序遍历也会not guarantee uniqueness。