java - 二叉搜索树中的递归 toString() 方法。这个的时间复杂度是多少？

Question

我是 Java 初学者，正在寻求帮助。

所以我用 Java 制作了这个二叉树，并且我应该实现一个方法，该方法按顺序对所有元素进行排序并将它们转换为字符串。应该很像前任吧“[1,2,3,4]”。我使用 StringBuilder 来做到这一点。

我的方法代码看起来像这样:

/**
 * Converts all nodes in current tree to a string. The string consists of
 * all elements, in order.
 * Complexity: ?
 * 
 * @return string
 */
public String toString() {
    StringBuilder string = new StringBuilder("[");
    helpToString(root, string);
    string.append("]");
    return string.toString();
}

/**
 * Recursive help method for toString. 
 * 
 * @param node
 * @param string
 */
private void helpToString(Node<T> node, StringBuilder string) {
    if (node == null)
        return; // Tree is empty, so leave.

    if (node.left != null) {
        helpToString(node.left, string);
        string.append(", ");
    }

    string.append(node.data);

    if (node.right != null) {
        string.append(", ");
        helpToString(node.right, string);
    }
}

所以我的问题是，如何计算时间复杂度？另外，如果有任何关于如何改进此方法的建议，我将非常感激。

Answer 1

最简单的答案是:O(n)。您访问每个节点一次并执行一 (a) 量的工作。计算结果如下

O(a*n)

因为我们忽略了常数因素，所以简单的答案是

O(n)

但是。也有人可能会争辩说，你只是多做了一点:每次访问没有叶子的地方时，你都会返回 null 。这又是一 (b) 项需要完成的工作。

让我们暂时称这些为隐形叶子。按照这个想法，树中的每个值都是一个节点，它有一个或两个不可见叶子。

现在，我们需要执行以下操作(对于每个节点):

a       | if a node has two child nodes
a + b   | if a node has one child node
a + 2b  | if a node has no child node.

对于最坏情况的二叉树(完全不平衡)，我们有 (n-1) 个带有一个子节点的节点和一个没有子节点的节点:

  "1"
    \
    "2"
      \
      "3"
        \
        "4"

因此，计算结果为

     (n-1)*(a+b) + b
 <=> an + bn - a - b + b
 <=> n(a+b) + b

  => O(an + bn)  // we ignore `+ b` because we always look at really big n's

幸运的是，即使在最坏的时间场景下，复杂度仍然是线性的。只有常数高于简单答案中的常数。在大多数情况下 - 通常当需要 Big-O 来比较算法时 - 我们甚至忽略这个因素，并且我们很高兴地说，算法时间复杂度是线性的 (O(n))。