binary-tree - BinaryTree 函数 - 复杂性

Question

我只是在写下不同的函数，这些函数是可以在二叉树上完成的操作。

我想知道这个函数的运行时间是多少，试图摆脱它们：

  getMaxDepth(Tree) //What can be the time complexity here? 
    if Tree.root = NIL return 0 // BaseCase
    leftDepth := 1 + getMaxDepth(Tree.root.left)
    rightDepth := 1 + getMaxDepth(Tree.root.right)
    if leftDepth > rightDepth then return leftDepth;
    else return rightDepth;


  internalNodeCount(Node n) // And here?
    if isLeaf(n) then return 0
    return 1 + internalNodeCount(n.left) + internalNodeCount(n.right)

  isLeaf(Node n)
    return n=NIL OR (n.left=NIL AND n.right=nil);

GetMaxDepth我假设时间复杂度是 O(n) 因为我需要递归地遍历整个树的每个节点......有什么好的解释？

InternalNodeCount 我猜它是相同的复杂度 O(n) 出于同样的原因.....

Answer 1

据我了解，您似乎正在寻找一些证据。

对于 getMaxDepth 这里是解释：

T(1) = c1
T(n) = T(k) + T(n-k-1) + c2
where
T(n) = Time to process tree of n nodes 
n = number of nodes
k = nodes in left subtree
n-k-1 = nodes in right subtree
c1, c2 = constants (not dependent upon n) 
(Time to calculate the depth of the tree from given left and right subtree depth)

除了 contants 会不同之外，同样可以应用于 internalNode 。