以下递归算法的运行时间？

我正在通过Gayle McDowell编写的“Cracking the coding interview”一书，并且遇到了一个有趣的递归算法，它将平衡二叉搜索树中所有节点的值相加。以下递归算法的运行时间？

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

现在盖尔说，运行时间为O（N），我发现，我看不出这个算法将永远结束混乱。对于一个给定的节点，当node.left在第一次调用中传递给sum时，然后node.right因此在第二次调用中传递给sum时，是不是第二次计算sum（节点）的算法？这个过程不会永远持续下去吗？对于递归算法，我还是个新手，所以它可能不是非常直观。

干杯！

来源

2016-10-19 lowentropy

'node.left'是'node'的左边子节点，'node.right'是正确的子节点。 'sum（node）'递归地计算左侧子节点的总和，然后右侧子节点并将它们加在一起（用'节点的值） –

这个过程不会永远持续下去。所讨论的数据结构是平衡二叉搜索树，而不是可以包含周期的图。

从根开始，所有节点将以-的方式探索，如深度优先搜索。

node.left将探索节点的左子树，node.right将探索同一节点的右子树。两个子树都没有相交。绘制程序控制轨迹以查看节点的探索顺序，并查看遍历中没有重叠。因为每个节点只被访问一次，递归将开始展开当一个叶节点将被命中时，运行时间将是O（N），N是节点的数量。

来源

2016-10-19 19:42:33 displayName

啊！所以node.right和node.left实际上是节点的子节点！这太让人感觉了！我现在看到为什么在递归调用中不能有循环行为。谢谢！ – lowentropy

-1

理解一个递归算法的关键是相信它做到了它所认为的。让我解释。

首先承认函数sum(node)返回以node为根的子树的所有节点的值的总和。

然后代码

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

可以做两两件事：

如果节点是null，返回0;这是一个非递归的情况，返回值是平凡的;
否则，该函数计算左子树的总和加上node的值加上右子树的总和，即以node为根的子树的总和。

因此，在某种程度上，如果函数是正确的，那么它是正确的:)其实参数不是圆形得益于非递归的情况下，这也是正确的。

我们可以用同样的推理方法来证明算法的运行时间。

假设处理以节点为根的树所需的时间与此子树的大小成比例，让|T|。这是另一种信仰行为。

然后，如果node为空，时间是不变的，让1单位。如果node不为空，则时间为|L| + 1 + |R|个单位，这正好是|T|。因此，如果对子树求和的时间与子树的大小成比例，则求和树的时间与树的大小成比例！

来源

2016-10-19 20:30:47

愚蠢downvote –

我不同意downvote，这是一个非常好的解释。当我的“声望”达到15时，我会回复upvote！ – lowentropy

以下递归算法的运行时间？

回答

相关问题