倾斜的二叉树与完美的二叉树-空间复杂度

Question

偏斜的二叉树是否比理想的二叉树占用更多空间？

我正在解决问题＃654-Leetcode上的最大二叉树，在给定一个数组的情况下，您必须制作一棵二叉树，使得根是数组中的最大数目，而左右子树在最大数左右两侧的子数组具有相同的原理，得出的结论是，在平均和最佳情况（完美的二叉树）中，占用空间为O（log（n）），最坏情况（偏斜）二叉树）将为O（n）。

例如，给定nums = [1,3,2,7,4,6​​,5]，树就这样，

      7
    /   \
   3     6
  /  \   / \ 
 1   2  4   5

并且如果给定nums = [7,6,5,4,3,2,1]，树就这样，

7
 \
  6
 / \
    5
   / \
      4
     / \
        3
       / \
          2
         / \
            1

根据我的理解，由于它们都具有n个节点，因此它们都应占用O（n）空间。所以我不明白他们是如何得出这个结论的。预先感谢。

Answer 1

https://leetcode.com/problems/maximum-binary-tree/solution/

在“空间复杂性”下，它说：

空间复杂度：O（n）。在最坏的情况下，集合的大小可以增长到n。在平均情况下，n个元素的大小将为nlogn（以num为单位），平均情况下复杂度为O（logn）。

措辞不好，但这是正确的。讨论的是树的构造过程中所需的内存量，而不是树本身占用的内存量。正如您正确指出的那样，树本身将占据O（n）空间，无论它是平衡的还是退化的。

考虑数组[1,2,3,4,5,6,7]。您希望根是最高编号，而左边则是数组最高编号左侧的所有内容。由于数组是按升序排列的，因此发生的是您提取了根的7，然后进行递归调用以构造左子树。然后，您提取6并进行另一个递归调用以构造该节点的左子树。您继续进行递归调用，直到放置1。总共有六个嵌套的递归调用：O（n）。

现在看看如果您的初始数组为[1,3,2,7,5,6,4]会发生什么。首先放置7，然后使用子数组[1,3,2]进行递归调用。然后，放置3并进行递归调用以放置1。您的树是：

             7
         3
       1

此时，您的通话深度为2。您返回并放置2。然后从两个递归调用中返回。树现在是：

             7
         3
       1   2

构造右子树还需要2的调用深度。任何时候调用深度都不得超过2。那是O（log n）。

事实证明，调用堆栈的深度与树的高度相同。理想树的高度为O（log n），简并树的高度为O（n）。