破解编码面试 - 示例 9（运行时示例）

Question

这个问题与二叉搜索树的深度有关，但我的问题是关于理解下面显示的示例代码：

int sum(Node node) {
    if (node == null){
        return 0;
    }
    return sum (node.left) + node.value + sum(node.right);
}

作者说这个深度大概是log N，不知道log N是怎么得的

还有，我对这段代码的理解，好像是无穷无尽的。我知道不是，但我无法说服自己。比如这是1~3的数组，节点从@2开始，所以：

LVL 1:sum(1)+2+sum(3)

LVL 2:sum(总和(0)+1+总和(2))+2+总和(总和(2)+3+总和(0))

LVL 3: ...（sum(2) 将重复 LVL 1，并且永远不会结束）

谁能帮我指出问题？

谢谢！

Answer 1

决定将我的评论变成答案：

二叉树是 log n，因为你每次都将它切成两半，但这是针对平衡树。例如，如果一切都在右边，一个非常不平衡的将是 O(N)。

那么，为什么它不是无限的？

由于这是递归的，它需要一种停止调用自身的方法，即当节点为空时，它会退出。

因此，在每棵树中，您最终都会到达未设置的子节点，这些将停止递归，从而防止递归无限。

如果删除该 if 语句，则会出现异常，但在递归算法中，如果实际上正在执行不会结束的操作，则会出现堆栈溢出。

Cracking the Coding Interview - Example 9 (Runtime Example)