Binary Tree遍历
题目列表
- pre-order
- in-order
- post-order
问题描述
有三种解法
- recursive
- iterative用stack
- Morris解法，不用stack,非递归，O(1)的空间（这个需要理解一下）
我们知道正常的遍历时间复杂度是O(n).空间复杂度是递归栈（或者自己维护的栈）的大小O(logn)
有的时候这不能满足面试官，就要用到moriss的方法，这种方法不需要栈来维护，所以只需要O(1)的空间
真实面经
有人被问到如果用O(1)的空间复杂度进行层遍历，我们已经知道了O(1)的pre-order, in-order, post-order的，对moriss的方法再进行改编一下