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

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) .