我相信在 Java 中镜像二叉树是直截了当的，例如：
http://stackoverflow.com/questions/4366251/mirror-image-of-a-binary-tree
但是，我遇到了一个面试问题，该问题与 Java 中的多线程有关，即阻塞队列（java.util.concurrent）
据我所知，我没有看到这两个概念之间有明显的联系，有人能给我暗示我可能遗漏了什么吗？谢谢！
问问题
116 次
1 回答
0
一般来说
树镜像的递归结构揭示了解决方案。首先给定根节点，我们在主线程上交换左孩子和右孩子。现在我们在左侧节点上应用镜像，在右侧节点上应用镜像。但是镜像左节点独立于镜像右节点，所以我们可以在不同的线程上进行。
保持以下规则以避免线程过多。当前线程交换它当前正在操作的节点的左右子节点。然后它将新左子节点的镜像委托给一个新线程，并继续处理右节点的镜像。
请注意，对于我们遇到的每个节点，我们都在生成一个新线程。因此，如果树不平衡并且只有左子节点，我们会生成 O(n) 个线程，其中 n 是树中的节点数。但是，我们可以维护一个线程池，这样一旦任何线程到达叶节点，它就会返回到池中。如果树是平衡的，每个线程都会在 O(log n) 步骤中终止，所以我们有 O(n / log n) 个线程的顺序（我认为？）。
使用阻塞队列
你可以结合这个线程池的想法来使用阻塞队列，通过将交换后的左右节点放入队列中，然后工作人员可以将它们取出并处理它们，然后返回该子节点的新左右子节点回到队列中等待另一个线程处理。一旦一个叶子节点被命中，就没有左右孩子了，所以队列中没有任何东西。当Queue为空时，镜像完成。
于 2013-04-09T09:08:58.703 回答