Cod*_* Ma 2 algorithm recursion binary-tree
我的一个朋友有以下面试问题,我们都不确定正确的答案是什么.有没有人知道如何处理这个问题？
给定不平衡二叉树,描述一种算法以随机选择节点,使得每个节点具有相同的被选择概率.
你可以通过一次树的传递来做到这一点.该算法与列表相同.
当您看到树中的第一个项目时,将其设置为所选项目.
当你看到第二个项目时,你会在范围(0,2)中选择一个随机数.如果它是1,那么新项目将成为所选项目.否则你跳过该项目.
对于您看到的每个节点,您可以增加计数,并按概率1 /计数选择它.因此,在第101个节点,您可以选择范围内的随机数(0,101).如果它是100,则该节点是新选择的节点.
完成遍历树后,返回选定的节点.该操作在时间上是O(n),其中n是树中的节点数,空间中是O(1).无需预处理.