图像数据结构
图像（方形图像）可以存储为树：如果图像是白色，则节点为白色，如果图像为黑色，则节点为黑色，如果包含两者，则为混合。白色和黑色节点是叶子，而混合节点将恰好有 4 个子节点，代表图像中的 4 个象限。给定 2 个图像（树），找到代表它们交集的图像。 （交集：B^B -> B、B^W -> W、W^W->W） 这是谷歌面试问题
An image(square image) can be stored as a tree: A node is white if the image is white, is black if the image is black, and is mixed if it contains both. White and black nodes are leaves, whereas a mixed node will have exactly 4 children, representing the 4 quadrants in the image. Given 2 images (trees), find the image representing their intersection. (Intersection: B^B -> B, B^W -> W, W^W->W)
This is a Google Interview Question
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是一个简单的方法：使用相同的顺序同时遍历两棵树。在执行此操作时构建输出树。然后：
这有可能创建一个实际上的混合节点只有白人孩子，所以你可能需要一个压缩步骤，遍历树折叠只有白人孩子的混合节点。
编辑：我认为您可以通过让递归知道下面是否找到输出黑色节点（如果答案是否定的，则放入白色叶子）来避免压缩步骤。
Here's a simple way to do it: Traverse both trees at the same time, using the same ordering. Build up an output tree while you do that. Then:
This has the possibility to create a mixed node that's actually only got white children, so you probably want a compression step where you traverse the tree collapsing mixed nodes that only have white children.
Edit: I think you could avoid the compression step by letting your recursion know whether output black nodes were found below (and putting in a white leaf if the answer was no).
由于两者都表示为二叉树，因此您必须从根开始遍历树结构，并随时检查两棵树中节点的颜色并将结果存储在另一棵树中。如果其中一个是黑色或白色，您将停止进一步遍历。否则，如果其中任何一个是混合的，则在该节点中进一步遍历，直到找到它们都是单色的。
Since both are represented as a binary tree you have to traverse a tree structure starting from root and check whats the color of nodes in both trees at any time and store the result in another tree. If either are black or white you stop traversing further. Else if anyone of them is mixed traverse further in that node until you find both of them of single color.