二叉树的Morris遍历方法

对于二叉树的先序、中序、后序遍历问题，我们一般使用递归或者非递归的方法实现，但是都无法做到额外空间复杂度为O(1)。这是因为遍历二叉树的递归方法实际使用了函数栈，而非递归方法则使用了申请的栈。两者的额外空间都与树的高度h相关，所以空间复杂度为O(h)。
但是，本题中使用的Morris遍历方法可以做到额外空间复杂度为O(1)，方法是使用二叉树节点中大量指向null的指针，本方法由Joseph Morris于1979年发明。