Binary Tree和Binary Search Tree的递归写法空间复杂度？

通常递归写法的空间复杂度到底是O(h)还是O(logn)? 被搞糊涂了。

?? 什么的复杂度??

空间复杂度还是时间复杂度？ 时间复杂度的话, h其实就是binary tree的高度，也就是lgn，LZ你说的两个其实是一个意思……

logn的空间复杂度可以当做常数空间。

尽量用tail recursion

weixc1234 发表于 2014-5-10 08:48
空间复杂度还是时间复杂度？ 时间复杂度的话, h其实就是binary tree的高度，也就是lgn，LZ你说的两个其实是 ...

我是指recursion所用的stack空间复杂度...

应该是O(N)吧，N是指所有节点的数目，说到底还是要用array来存的。