具有递归的二叉树中计数节点的时间复杂度是否比 o(n) 正确？
The time complexity of count nodes in a binary tree with recursion, is a little more than o(n) correct?
以这段python代码为例
def count_nodes(node: Node):
if(node is None):
return 0
return 1 + count_nodes(node.left) + count_nodes(node.right)
在叶子上，递归将指向左和右，return 0
在一个非常大的二叉树中，时间复杂度将是：
o(n) + the number of leafs * 2
对吗？或者我误解了时间复杂度
在这个例子中，你附加了你只遍历那些有效的（或存在的）节点，所以在这种情况下，如果你有 n 个节点，你只遍历 n 个节点。
这样写是没有错的：o(n) + the number of leafs * 2 但最终它会变成：o(n) 就 Big-O 而言。
以这段python代码为例
def count_nodes(node: Node):
if(node is None):
return 0
return 1 + count_nodes(node.left) + count_nodes(node.right)
在叶子上，递归将指向左和右，return 0
在一个非常大的二叉树中，时间复杂度将是：
o(n) + the number of leafs * 2
对吗？或者我误解了时间复杂度
在这个例子中，你附加了你只遍历那些有效的（或存在的）节点，所以在这种情况下，如果你有 n 个节点，你只遍历 n 个节点。
这样写是没有错的：o(n) + the number of leafs * 2 但最终它会变成：o(n) 就 Big-O 而言。