algorithm - 找到二叉树的最大深度时的最坏情况

这是寻找二叉树最大深度的伪代码：

 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）。这种算法最坏的情况是什么？为什么？

最佳答案

正如你在你的问题中指出的，以及其他人在评论中指出的，你的算法的运行时复杂度是O（n）。它总是访问所有节点。
然而，空间复杂性是不同的。递归深度取决于树的深度。如果树是完全平衡的，那么递归深度是o（log n）。如果树是退化的，也就是说，每个节点只有一个子-那么递归深度，因此空间复杂度也是O（n）。
这是一个巨大的不同想象一棵有一百万个节点的树。如果它是平衡的，空间需求大约是20个堆栈帧。如果树是严重不平衡的，则空间需求接近100万个堆栈帧。
你的问题的答案是，运行时复杂度是O（n），空间复杂度是O（log n）在平均情况下（合理平衡的树），和O（n）在最坏的情况下。