二叉树的普通遍历算法有很多，但它们都无法做到额外空间复杂度O(1)，因为它们总要用到栈来保存信息，才能够从下层回到上层。这里介绍Morris遍历，能够做到时间复杂度为O(n)，额外空间复杂度为O(1)。
Morris中序遍历
Morris遍历其实就是利用了树中大量的null指针。如下图，我们现在先来考虑中序遍历，对于节点4，什么时候会打印它呢？
由中序遍历的序列得知，在节点4的左子树都打印完毕后，才会轮到节点4，接着就是节点4的右子树了。因为节点4的左子树最后一个打印的节点是左子树的最右节点3，那么我们先把这个节点的right指针指向节点4，当打印到该点时，不就可以顺着右指针回到节点4了。
所以Morris中序遍历的流程大概如此：
⑴对于一个节点cur，找到它左子树的最右节点，看这个节点的right指针是null还是指向cur。
⑵如果是null，说明左子树还没处理过，更新该指针为cur，然后进入左子树继续上述流程。
⑶如果该指针已经是cur了，说明左子树已经处理完毕，现在是处理完毕后顺这最右节点的right指针回到该cur节点的，需先将该right指针恢复为null，处理该cur节点后进入右子树重复流程⑴。
代码：
void MorrisInOrder(Node* head){if (head == nullptr)return;// 当前遍历到节点
Node* cur = head;// 左子树的最右节点
Node* next;while (cur){// 处理左子树的最右节点
next = cur->left;if (next){while (next->right && next->right != cur)
next = next->right;// 不等于cur，说明未遍历过，设置线索，并跳到该左子树if (next->right != cur){
next->right = cur;
cur = cur->left;continue;}// 否则说明该左子树已处理完毕，恢复原指针else{
next->right = nullptr;}}// 该节点的左子树已处理完毕，转向右子树
cout << cur->value << " ";
cur = cur->right;}}先序遍历
先序遍历只是在中序遍历的基础上调整了一下打印时机，在第一次遍历到节点时就打印该节点。
void MorrisPreOrder(Node* head){if (head == nullptr)return;
Node* cur = head;
Node* next;while (cur){
next = cur->left;if (next){while (next->right && next->right != cur)
next = next->right;if (next->right != cur){
cout << cur->value << " ";
next->right = cur;
cur = cur->left;continue;}else{
next->right = nullptr;}}else{
cout << cur->value << " ";}
cur = cur->right;}}后序遍历
同样，后序遍历也是中序遍历的变种，但其调整更加复杂。
简单来说就是，对于一个节点，先处理左子树，但并不是把整棵左子树都处理完，而是留下该左子树的右边界，当回到该节点时，才逆序打印整个右边界，这样左子树就处理完了。
这时回到该节点但并不处理该点，而是直接进入右子树处理，待到右子树顺着最右节点回到上层父节点时，该节点才做为上层父节点的左子树右边界被打印。
如下图，对于节点4，先处理左子树的非右边界节点1，待到回到节点4才处理左子树的右边界节点3、2。
右边界的处理方法：先把边界的右指针逆序，依次打印后，重新逆序恢复。
代码：
Node* ReverseEdge(Node* head){
Node* cur = head;
Node* pre = nullptr;
Node* next;while (cur){
next = cur->right;
cur->right = pre;
pre = cur;
cur = next;}return pre;}void PrintEdge(Node* head){
Node* tail = ReverseEdge(head);
Node* cur = tail;while (cur){
cout << cur->value << " ";
cur = cur->right;}ReverseEdge(tail);}void MorrisPosOrder(Node* head){if (head == nullptr)return;
Node* cur = head;
Node* next;while (cur){
next = cur->left;if (next){while (next->right && next->right != cur)
next = next->right;if (next->right != cur){
next->right = cur;
cur = cur->left;continue;}else{
next->right = nullptr;PrintEdge(cur->left);}}
cur = cur->right;}PrintEdge(head);}