相比传统的递归和非递归遍历方法，Morris遍历优点为：空间复杂度为 O(1) ，也就是 非递归、不用栈 。 它是依靠二叉树中叶子结点有空指针，对叶子结点的儿子不断地添加线索，删除线索来实现遍历。

中序遍历

步骤：
1. 如果当前节点 cur 的左孩子为空，则输出当前节点并将右孩子作为当前节点。
2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点 pre 。
a) 如果前驱节点 pre 的右孩子为空，将当前节点 cur 设置为pre 的右孩子。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。
3. 重复以上1、2直到当前节点为空。

Morris遍历二叉树（空间复杂度O(1)） - 图1

  1. TreeNode *cur = root, *pre = nullptr;
  2. while (cur) {
  3.     // 情况1：当前结点的左孩子不存在
  4.     if (!cur->left) {   
  5.         visit(cur);  // 拜访当前结点
  6.         cur = cur->right;
  7.         continue;
  8.     }
  9.     // 情况2：当前结点的左孩子存在
  10.     pre = cur->left;
  11.     while (pre->right && pre->right != cur) {
  12.         pre = pre->right;
  13.     }
  14.     // 情况2(a)
  15.     if (!pre->right) {
  16.         pre->right = cur;
  17.         cur = cur->left;
  18.     } 
  19.     // 情况2(b)
  20.     else {
  21.         pre->right = nullptr;
  22.         visit(cur);
  23.         cur = cur->right;
  24.     }
  25. }

前序遍历

与中序遍历相比，只是在输出当前结点上有了一个变化。

步骤：
1. 如果当前节点 cur 的左孩子为空，则输出当前节点并将右孩子作为当前节点。
2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点 pre 。
a) 如果前驱节点 pre 的右孩子为空，将当前节点 cur 设置为pre 的右孩子。输出当前节点。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。
3. 重复以上1、2直到当前节点为空。

代码也是几乎一样

  1. TreeNode *cur = root, *pre = nullptr;
  2. while (cur) {
  3.     // 情况1：当前结点的左孩子不存在
  4.     if (!cur->left) {   
  5.         visit(cur);  // 拜访当前结点
  6.         cur = cur->right;
  7.         continue;
  8.     }
  9.     // 情况2：当前结点的左孩子存在
  10.     pre = cur->left;
  11.     while (pre->right && pre->right != cur) {
  12.         pre = pre->right;
  13.     }
  14.     // 情况2(a)
  15.     if (!pre->right) {
  16.         pre->right = cur;
  17.         visit(cur);
  18.         cur = cur->left;
  19.     } 
  20.     // 情况2(b)
  21.     else {
  22.         pre->right = nullptr;
  23.         cur = cur->right;
  24.     }
  25. }

后序遍历

在借助栈的非递归中，后序遍历蛮复杂的，在Morris遍历中也是如此。
我们可以先考虑一种奇技淫巧：
后序遍历也就是后根序遍历，遍历顺序为“左右根”，根在后面不好处理，那我们可以遍历得到“根右左”，然后对输出的序列进行翻转。这种方式是比较简单的，和前根序遍历差不多，只不过把左右置换了一下，并且最后翻转输出序列。

“根右左”遍历步骤：
1. 如果当前节点 cur 的右孩子为空，则输出当前节点并将左孩子作为当前节点。
2. 如果当前节点的右孩子不为空，在当前节点的右子树中找到当前节点在“右根左”遍历下的前驱节点 pre 。
a) 如果前驱节点 pre 的左孩子为空，将当前节点 cur 设置为pre 的左孩子。输出当前节点。当前节点更新为当前节点的右孩子。
b) 如果前驱节点的左孩子为当前节点，将前驱结点的左孩子重新设为空（恢复树的形状）。当前节点更新为当前节点的左孩子。
3. 重复以上1、2直到当前节点为空。

再将上述输出序列翻转即可得到后序遍历。

当然了，正统方法是这样的。
与中序遍历相比只是2(b)步骤输出时不同。

步骤：**
1. 如果当前节点 cur 的左孩子为空，则输出当前节点并将右孩子作为当前节点。
2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点 pre 。
a) 如果前驱节点 pre 的右孩子为空，将当前节点 cur 设置为pre 的右孩子。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。倒序输出从当前节点的左子节点到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右孩子。
3. 重复以上1、2直到当前节点为空。

  1. void addPath(vector<int> &vec, TreeNode *node) {
  2.         vector<int> tmp;
  3.         while (node != nullptr) {
  4.             tmp.emplace_back(node->val);
  5.             node = node->right;
  6.         }
  7.         reverse(tmp.begin(), tmp.end());
  8.         for (auto &it : tmp) {
  9.             vec.emplace_back(it);
  10.         }
  11.     }
  13.     vector<int> postorderTraversal(TreeNode *root) {
  14.         vector<int> res;
  15.         if (root == nullptr) {
  16.             return res;
  17.         }
  19.         TreeNode *p1 = root, *p2 = nullptr;  // p1是当前结点，p2是前驱结点
  21.         while (p1 != nullptr) {
  22.             p2 = p1->left;
  23.             if (p2 != nullptr) {
  24.                 while (p2->right != nullptr && p2->right != p1) {
  25.                     p2 = p2->right;
  26.                 }
  27.                 if (p2->right == nullptr) {
  28.                     p2->right = p1;
  29.                     p1 = p1->left;
  30.                     continue;
  31.                 } else {
  32.                     p2->right = nullptr;
  33.                     addPath(res, p1->left);
  34.                 }
  35.             }
  36.             p1 = p1->right;
  37.         }
  38.         addPath(res, root);
  39.         return res;
  40.     }

参考文章

Morris中序遍历简述
Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）
力扣官方题解之二叉树的后序遍历