同一子树的二叉树压缩
给定一棵树，找到公共子树并替换公共子树并压缩树。 例如，
1
/ \
2 3
/ | /\
4 5 4 5
应该转换成
1
/ \
2 3
/ | /\
4 5 | |
^ ^ | |
|__|___| |
|_____|
我在采访中被问到 这个。我分享的方法不是最优的 O(n^2)，如果有人可以帮助解决或将我重定向到类似的问题，我将不胜感激。我找不到任何。谢谢！
编辑-更复杂，例如：
1
/ \
2 3
/ | /\
4 5 2 7
/\
4 5
以 2 为根的整个子树应该被替换。
1
/ \
2 <--3
/ | \
4 5 7
Given a tree, find the common subtrees and replace the common subtrees and compact the tree.
e.g.
1
/ \
2 3
/ | /\
4 5 4 5
should be converted to
1
/ \
2 3
/ | /\
4 5 | |
^ ^ | |
|__|___| |
|_____|
this was asked in my interview. The approach i shared was not optimal O(n^2), i would be grateful if someone could help in solutioning or redirect me to a similar problem. I couldn't find any. Thenks!
edit- more complex eg:
1
/ \
2 3
/ | /\
4 5 2 7
/\
4 5
whole subtree rooted at 2 should be replaced.
1
/ \
2 <--3
/ | \
4 5 7
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以使用
(value, left_pointer, right_pointer) -> 中的哈希映射在一次 DFS 遍历中完成此操作。节点折叠重复出现的子树。当您将每个节点留在 DFS 中时，您只需在地图中查找它即可。如果匹配的节点已存在，则将其替换为先前存在的节点。否则，将其添加到地图中。
这需要 O(n) 时间，因为您正在比较实际指针与左 + 右子树，而不是遍历树来比较它们。指针比较给出相同的结果，因为左子树和右子树已经被规范化。
You can do this in a single DFS traversal using a hash map from
(value, left_pointer, right_pointer) -> nodeto collapse repeated occurrences of the subtree.As you leave each node in your DFS, you just look it up in the map. If a matching node already exists, then replace it with the pre-existing one. Otherwise, add it to the map.
This takes O(n) time, because you are comparing the actual pointers to the left + right subtrees, instead of traversing the trees to compare them. The pointer comparison gives the same result, because the left and right subtrees have already been canonicalized.
首先，我们需要存储哈希表中出现的节点值。如果树已经存在，我们可以迭代树，如果节点值已经在节点集中，则删除该节点的分支。否则，将值存储在哈希映射中，每次创建新节点时，检查该值是否出现在映射中。
Firstly, we need to store the node values that appear in a hash table. If the tree already exists, we can iterate the tree and if a node value is already in the set of nodes and delete the branches of that node. Otherwise, store the values in a hash map and each time, when a new node is made, check if the value appears in the map.