我的一位朋友遇到了以下面试问题，我们都不太确定正确答案是什么。有谁知道如何解决这个问题？
给定一个不平衡二叉树，描述一种随机选择节点的算法，使得每个节点被选择的概率相等。
您只需遍历树一次即可完成此操作。该算法与列表相同。
当您看到树中的第一个项目时，您将其设置为选定的项目。
当您看到第二个项目时，您在 (0,2] 范围内选择一个随机数。如果它是 1，则新项目将成为所选项目。否则您将跳过该项目。
对于您看到的每个节点，您增加计数，并以 1/计数的概率选择它。因此，在第 101 个节点，您在 (0,101] 范围内选择一个随机数。如果它是 100，则该节点是新选定的节点。
遍历完树后，返回选定的节点。该操作的时间复杂度为 O(n)，其中 n 是树中的节点数，空间复杂度为 O(1)。无需预处理。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
