数据结构与算法——二叉树的Morris遍历二叉树的Morris遍历
二叉树的Morris遍历在二叉树的递归遍历中,有函数的递归调用,递归的深度等于二叉树的高度,也就是说递归导致的调用堆栈的高度等于二叉树的高度,这样的话,程序虽然没有显示的通过new 来分配内存,但实际上消耗的内存大小也是 O(h). 如果二叉树的高度很大,例如搜索引擎把几十亿张网页按照权重来组成二叉树的话,那么二叉树的高度也要几十万作用,因此按照传统的中序遍历,需要消耗大量的内存。下面要讲的M...