求教一个tree的题和其复杂度分析

leetcode 108题 用recuisive的情况下，time 和space究竟是O(N)还是O(logN)?
有的帖子说是logN因为balanceBST

但是我考虑到递归方法是不是都要遍历所有elements？

谢谢大家~


求点米。。

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. Example: Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:       0      / \    -3   9    /   /  -10  5

Luffy_Tse 发表于 2019-9-24 15:28
time是O(N), 因为对于每个element你都要去建立一个TreeNode，也就是你需要遍历所有节点。 extra space是O(l ...

解法的话 我们就先讨论下面这个解法

1. class Solution:
   
2.     def sortedArrayToBST(self, nums):
   
3.         if not nums:
   
4.             return None
   
5.         mid = len(nums) // 2
   
6.         root = TreeNode(nums[mid])
   
7.         root.left = self.sortedArrayToBST(nums[:mid])
   
8.         root.right = self.sortedArrayToBST(nums[mid+1:])
   
9.         return root

复制代码

乐观的小天使 发表于 2019-9-25 02:48
space复杂度是根据层数？为什么不是根据node数呢？因为每个node都要进一次stack吧？

所以我才加了extra space，根据node的话一共有N个node，所以这边的复杂度是O(N)，你答案就需要这么多，这个你没办法优化。
你也说对了，是需要stack，这个stack是程序执行的时候recursive call 产生的。但是这个stack的大小并不是随着每个node的生成就一直增加的 -> 这个stack除了push还有pop -> 你的解法return到上一级的时候就是pop。

楼主最后能把题帖一下，这样大家看着方便.

同问，最好贴下题

time是O(N), 因为对于每个element你都要去建立一个TreeNode，也就是你需要遍历所有节点。 extra space是O(logN)，当然还看你是怎么recursive的，正常的会用left & right idx，也有不正常的直接copy一份subarray。正常解法的话因为是balanceBST，高度就是logN，所以recursive产生的层数就是logN -> extra space O(logN)。

看起来是avl tree的要求嘛。正常情况下time难道不是O(n logn)吗？avl tree每个node的正常insertion要O(log n)，这里有n个nodes.所以总和是O(n log n).

当然如果有优化，更充分利用原array已被sorted的特性，直接生成一个complete tree,那样子可能是O(n). O(log n)不可想像，因为毕竟有n个数要处理啊。

Luffy_Tse 发表于 2019-9-24 15:28
time是O(N), 因为对于每个element你都要去建立一个TreeNode，也就是你需要遍历所有节点。 extra space是O(l ...

space复杂度是根据层数？为什么不是根据node数呢？因为每个node都要进一次stack吧？

乐观的小天使 发表于 2019-9-25 02:49
解法的话 我们就先讨论下面这个解法
[mw_shl_code=python,true]class Solution:
    def sortedArrayTo ...

这个解法你就要注意一下Python的数组切片是对原数组wrap一下还是说直接copy了一个新的数组。如果是前者的话你的extra space就是O(logN)，后者的话就是O(N)。
我的印象里面python数组切片是浅拷贝，所以你给的这个解法应该是O(N) extra space。优化的话建议用idx而不是用切片。