java - 在 O(logn) 中打印二叉树中的随机元素

Question

给定一个带有 TreeNode 的二叉树，如下所示:

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    int size;
}

其中size是(左子树+右子树+1)中的节点数。

Print a random element from the tree in O(logn) running time.

注意:这篇文章不同于this第一，正如明确提到的那样，我们有一个与此问题中的每个节点关联的 size。

PS:写这篇文章的灵感来自 this .

Answer 1

有一种简单的方法可以提供 O(n) 的复杂度。

• 生成一个范围在 1 到 root.size 之间的随机数
• 做一个BFS或 DFS遍历
• 在 random numbered 处停止迭代元素并打印出来。

为了提高复杂性，我们需要在每次迭代时创建自己的分支顺序，而不是像 BFS 和 DFS 中那样按顺序进行。我们可以使用 size每个节点的属性决定是遍历左子树还是右子树。以下是方法:

• 生成一个范围在 1 到 root.size 之间的随机数(说 r )
• 从根节点开始遍历，决定是去左子树、右子树还是打印根:
  • 如果r <= root.left.size , 遍历左子树
  • 如果r == root.left.size + 1 , 打印根(我们已经找到要打印的随机节点)
  • 如果r > root.left.size + 1 ,遍历右子树
• 本质上，我们定义了一个顺序，其中当前节点的排序为(当前节点的左子树的大小)+ 1。
• 由于我们消除了在每次迭代时遍历左子树或右子树，因此其运行时间为 O(logn)。

伪代码看起来像这样:

traverse(root, random)
  if r == root.left.size + 1
    print root        
  else if r > root.left.size + 1
    traverse(root.right, random - root.left.size - 1)
  else
    traverse(root.left, random)

Java实现如下:

public static void printRandom(TreeNode n, int randomNum) {
    int leftSize = n.left == null ? 0 : n.left.size;
    if (randomNum == leftSize + 1)
        System.out.println(n.data);
    else if (randomNum > leftSize + 1)
        printRandom(n.right, randomNum - (leftSize + 1));
    else
        printRandom(n.left, randomNum);
}