二叉搜索树中的递归 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 。这又是一项需要完成的工作。

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

现在，我们需要执行以下操作（对于每个节点）：

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))。

Answer 2

时间复杂度为 O(n)，因为您访问每个节点一次。为了在树上行走，你没有比这更好的了。

Answer 3

时间复杂度与树中节点的数量成线性关系：您只访问每个节点一次。