二叉树的前中后序遍历的空间复杂度是O（logN）
深度遍历的空间复杂度取决于树的高度，树的高度是h，栈的深度就是h乘以一个常数。最坏情况当然是O(n)的，但在随机情况下是不会发生的，只有在元素出现次序本身具有某些规律的情况才会发生。你的代码可能是这样的：void puttree(tree t){ if(t!=NULL){ put(t-\u0026gt;data); puttree(t-\u0026gt;left); puttree(t-\u0026gt;right); }}在有尾递归优化的情况下，最后一条语句不用压栈，不占用栈空间，因此空间复杂度为S(n)=S(left)+1在平衡的时候，left=n/2,S(n)=S(n/2)+1,得S(n)=O(logn)在树严重向左偏，left=n-1,S(n)=S(n-1)+1,得S(n)=O(n) 当树严重向右偏，left=1,S(n)=S(1)+1,得S(n)=O(1)
■网友
回答成O(h)就没问题了，h为二叉树高度
平均情况下，h=logn，即O(logn)
【二叉树的前中后序遍历的空间复杂度是O（logN）】 最坏情况下，h=n，即O(n)
■网友
平均是O(logN)但是最坏情况下退化成O(N)吧，当然如果用平衡树的话就能保证最坏也O(logN)了。
推荐阅读
- 目前中国还有哪些历史中重要人物的古墓没有被发掘
- 趣头条|要换全新前中网？MINI国内谍照曝光
- 二叉树c语言模块化实现要写头文件吗
- 二叉树代码bug
- 红黑树与普通的平衡二叉树除了颜色到底有啥区别为啥要引入红黑树，它比普通的平衡二叉树究竟好在哪
- wey|奔驰G500外观，配前中后三把差速锁，又一台坦克300越野版实车到店
- 二叉树的根节点深度为1还是0
- 民国时期|70多年前中国这所大学为什么会成为世界一流大学？
- 目前中国的哪个电商网站是绝对没假货的
- 汽车市场|全新途乐卷土重来，V8引擎+坦克掉头+前中锁，别等普拉多了