倾斜二叉树vs完美二叉树空间复杂度
一个倾斜的二叉树是否比一个完美的二叉树占用更多的空间？
我正在解决问题#654 - Leetcode上的最大二叉树，其中给定一个数组，你必须创建一个二叉树，使得根是数组中的最大数，最大数的右边和左边的子数组基于相同的原理生成二叉树，并且得出结论，在平均和最好的情况下(完美二叉树)，占用的空间将是O(log(n))，而最坏的情况(倾斜的二叉树)将是O(n)。
例如，给定数字= 1,3,2,7,4,6,5，树将是这样的，
7
/ \
3 6
/ \ / \
1 2 4 5如果给定的数字= 7,6,5,4,3,2,1，则树将是这样的，
7
\
6
/ \
5
/ \
4
/ \
3
/ \
2
/ \
1根据我的理解，它们都应该占用O(n)空间，因为它们都有n个节点。所以我不明白他们是怎么得出这个结论的。提前谢谢。
回答 1
Stack Overflow用户
发布于 2019-10-18 06:54:59
https://leetcode.com/problems/maximum-binary-tree/solution/
在“空间复杂性”下，它说：
空间复杂度: O(n)。在最坏的情况下，集合的大小可以增长到n。在平均情况下，n个元素的大小为nlogn，平均情况复杂度为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 )。
事实证明，调用堆栈的深度与树的高度相同。完美树的高度为O(log )，退化树的高度为O(n)。
https://stackoverflow.com/questions/58423815
复制相似问题
腾讯云开发者
