最糟糕的情况是找到二叉树的最大深度

Question

这是用于查找二叉树最大深度的伪代码:

 maxDepth(Node N)

1. If Nodes is leaf node then return 0

2. Else

     (a) Get the max depth of left subtree recursively  i.e., 

          call maxDepth( N->left-subtree)

     (a) Get the max depth of right subtree recursively  i.e., 

          call maxDepth( N->right-subtree)

     (c) Get the max of max depths of left and right 

          subtrees and add 1 to it for the current node.

         max_depth = max(max dept of left subtree,  
                             max depth of right subtree) 
                             + 1
     (d) Return max_depth

我对这个算法的最坏情况感到困惑.这个伪代码的复杂性将是O(n).这个算法的最坏情况是什么？为什么？

Answer 1

正如您在问题中指出的那样,以及其他人在评论中指出,算法的运行时复杂性为O(n).它总是访问所有节点.

然而,空间复杂性是不同的.递归深度取决于树的深度.如果树完全平衡,则递归深度为O(log n).如果树是退化的 - 也就是说,每个节点只有一个子节点 - 那么递归深度和空间复杂度也是O(n).

这会产生巨大的差异.想象一下拥有100万个节点的树.如果它是平衡的,则空间要求将是大约20个堆栈帧的量级.如果树严重不平衡,则空间要求接近100万个堆栈帧.

那么,你的问题的答案是运行时复杂度为O(n),空间复杂度在平均情况下是一个O(log n)(一个合理平衡的树),在最坏的情况下是O(n).