破解编码面试 - 示例 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开始，所以：

等级1：总和(1)+2+总和(3)

LVL 2：总和（总和（0）+1+总和（2））+2+总和（总和（2）+3+总和（0））

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

谁能帮我指出这个问题吗？

谢谢！

Answer 1

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

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

那么，为什么不是无限呢？

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

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

如果删除该 if 语句，那么您将得到一个异常，但在实际上正在做一些不会结束的事情的递归算法中，您将得到堆栈溢出。

Answer 2

我刚刚遇到了同样的事情。我一生都无法弄清楚为什么没有发布更多内容。只要你假设树有3个或更多节点，中间节点就会调用left，左节点就会调用它的left和right。然而，它的右边现在是原始节点。该节点将回调到其左侧，并且您将出现堆栈溢出。我这里错了吗？