对于二叉树的遍历分为三种：前序遍历(根左右)、中序遍历(左根右)、后序遍历(左右根)。假设一个树高为h的二叉树，三种遍历算法的时间复杂度都是O(n)，空间复杂度为O(h) 因为遍历二叉树的每一个节点，最好的情况就是每一个节点被访问一次，所以时间复杂度无法再优化，但是空间复杂度仍然可以优化。 二叉树的遍历算法可以使用递归和非递归来实现，递归会有隐式的调用堆栈，非递归使用额外的数据结构来支持。

哪如何在遍历过程中避免去申请额外的空间呢？我们知道对于一个拥有n个节点的二叉树，有2n个指针域，但是非空指针域有n-1个，空指针域有n+1个，这些空指针域能不能拿来用呢？ 线索二叉树就是首先对一棵二叉树变成一棵线索二叉树，线索二叉树就是将左孩子空指针域指向其前驱节点，右孩子空指针域指向其后继节点，莫里斯算法就是基于线索二叉树来实现O(1)空间复杂度的遍历。

我们首先将该二叉树变成线索二叉树如下: 可以看到对于节点的空指针域用来指向其前驱和后继节点，这样就将闲置的空间利用起来了，而不用堆栈保存上一层节点的位置，节省了空间。

如何寻找前序节点？ 如果当前节点有左孩子，那么从左孩子开始一直沿着右孩子指针一直往右走，直到走到叶子节点为止，该叶子节点即为当前节点的前序节点，例如节点6，首先移动到左孩子4，然后从该节点的右孩子移动到叶子节点5，5即是节点6的前序节点。

根据当前节点，找到其前序节点，如果该前序节点右孩子为空，咋将前序节点的右孩子指向当前节点，然后进入当前节点的左孩子;

如果当前节点的左孩子为空，访问该节点，然后进入其右孩子;

如果当前节点的前序节点的右孩子指向自身，将前序节点的右孩子设置为null，访问该节点，然后进入其右孩子。