前面讲的二叉树的DFS非递归遍历方式，需要一个栈。如果使用 Morris 遍历就不需要了，因为二叉树的叶子节点是没有子节点的，也就是说他们是指向空，这样总感觉有点浪费，Morris 的实现原理其实就是把叶子节点的指针给 利用了起来。
Morris 的遍历过程如下：
- 1，如果当前节点 cur 没有左子节点，让 cur 指向他的右子节点，即 cur=cur.right。
- 2，如果当前节点 cur 有左子节点，则找到左子节点最右边的节点 pre 。
- 1，如果 pre 的右子节点为空，就让 pre 的右子节点指向 cur ，即 pre.right=cur 。然后 cur 指向他的左子节点，即 cur=cur.left 。
- 2，如果 pre 的右子节点不为空（说明当前节点 cur 的左子树都被遍历完了，要把树给还原），就让他指向空，即 pre.right=null 。然后将节点 cur 指向其右子节点，即 cur=cur.right 。
- 3，重复 步骤 1，2 ，直到节点 cur 为空为止。
如果看不懂没关系，下面我们来一步步分析。
1，如果当前节点 cur 没有左子节点，让 cur 指向他的右子节点，即 cur=cur.right。
这个没啥可说的，没有左子节点了就只能访问右子节点了，如下图所示。
2，如果当前节点 cur 有左子节点，则从左子节点中找到最右边的结点 pre 。
这个是找到左子节点中最右边的节点 pre ，就是在 cur 的左子节点一直往右找，其实也就是中序遍历中 cur 的前一个节点，下面举几个例子看下，如下图所示。
2.1，如果 pre 的右子节点为空，就让 pre 的右子节点指向 cur ，即 pre.right=cur 。然后 cur 指向他的左子节点，即 cur=cur.left 。
这个很容易理解，如果当前节点 cur 的左子树还没有被访问的话，那么 pre 的右指针肯定是为空的，如果他不为空，肯定会一直往右边找下去的。所以如果 pre 的右指针为空的话，让 pre 的右指针指向 cur ，也就是 pre.right=cur，相当于串成了一个环，如下图所示。
2.2，如果 pre 的右子节点不为空，就让他指向空，即 pre.right=null 。并将节点 cur 指向其右子节点，即 cur=cur.right 。
如果 pre 的右指针不为空，那么他肯定是指向节点 cur 的，这个时候说明当前节点 cur 的左子树都已经访问完了，我们需要把这棵树给还原，让 pre 的右指针指向空。这就是二叉树的 Morris 遍历，我们来看下代码：
public void morrisTraversal(TreeNode root) {
TreeNode cur = root;// 记录当前访问的节点。
while (cur != null) {
if (cur.left == null) {
// System.out.println(cur.val); 打印位置 1
// 如果当前节点cur没有左子节点，让cur指向他的右子节点。
cur = cur.right;
} else {
// 如果cur有左子节点，要找到左子树的最右节点pre。
TreeNode pre = cur.left;
// 查找pre节点，注意这里有个判断就是pre节点不能等于cur。
while (pre.right != null && pre.right != cur)
pre = pre.right;
// System.out.println(cur.val); 打印位置 2。
// 如果pre节点的右指针指向空，说明cur的左子树没被访问。
if (pre.right == null) {// 第一次到当前节点（重要，先记住）。
pre.right = cur;// 串成环。
cur = cur.left;// 继续访问cur的左子树。
} else {// 第二次到当前节点（重要，先记住）。
// 如果pre的右指针不为空，那么他肯定是指向cur的,表示节
// 点cur的左子树都访问完了，然后访问他的右子节点。
pre.right = null;
cur = cur.right;
}
}
}
}
这个就是按照上面步骤总结的代码，其中有两行代码被我注释掉了，分别是打印位置 1 和打印位置 2 ，我们把这两行代码放开，对下面这棵树进行打印如下图所示：
打印的结果如下：
[1, 2, 4, 2, 5, 1, 3, 6]
我们发现有些节点被打印了一次有些节点被打印了两次，那么哪些节点会被打印两次呢，细心的同学可能已经发现了，只要有左子节点的都会被打印两次，比如图中节点 [1，2] ，因为他们有左子节点，所以被打印两次，没有左子节点的都只能被打印一次，比如图中节点 [4，5，3，6] 。
因为当前节点如果没有左子节点，那么当前节点只会被访问一次然后就到他的右子节点了。如果当前节点有左子节点，那么当前节点访问完之后会到他的左子节点，而他的左子节点访问完之后又会回到当前节点，所以会访问两次，我们来看下 Morris 前序和中序遍历的顺序（Morris 的后序遍历有点复杂，这个放在后面单独讲）：
- 如果当前节点没有左子节点，在前序和中序遍历中直接打印当前节点。
- 如果当前节点有左子节点，那么在Morris遍历中当前节点会被访问两次：
- 在前序遍历中，先访问当前节点在访问左子节点，所以第一次到当前节点的时候打印，第二次到当前节点的时候不要打印。
- 在中序遍历中，先访问左子节点在访问当前节点，所以第一次到当前节点的时候不要打印，第二次到当前节点的时候在打印。
因为在前序遍历中第一次到当前节点的时候，左子树还没打印，直接打印当前节点即可。但中序遍历中必须要等左子树打印完之后才能打印当前节点，所以必须要等第二次到当前节点的时候才能打印，因为第二次到当前节点的时候，他的左子树都已经打印完了。我们把重复的结果删除掉再来看下，如下图所示。
对于没有左子节点的只能被访问一次，不会出现重复。对于有左子节点的，我们怎么确定当前节点是第一次出现还是第二次出现呢，其实很简单，如果是第一次出现，那么他的 pre 节点的右指针必定是指向空的。如果是第二次出现，那么他的 pre 节点的右指针一定不为空。所以如果当前节点的左子节点不为空，我们可以根据 pre 节点的右指针是否为空来判断当前节点是第一次出现还是第二次出现。
对于前序遍历就是：
- 如果当前节点 cur 没有左子节点，直接打印当前节点 cur 的值。
- 如果 pre 节点的右指针为空，也打印当前节点 cur 的值。
来看下代码。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> preList = new ArrayList<>();
TreeNode cur = root;// 记录当前访问的节点。
while (cur != null) {
if (cur.left == null) {
preList.add(cur.val);// 1，没有左子节点打印。
cur = cur.right;
} else {
TreeNode pre = cur.left;
while (pre.right != null && pre.right != cur)
pre = pre.right;
if (pre.right == null) {// 第一次到当前节点。
preList.add(cur.val);// 2，pre节点的右指针为空。
pre.right = cur;
cur = cur.left;
} else {// 第二次到当前节点。
pre.right = null;
cur = cur.right;
}
}
}
return preList;
}
对于中序遍历就是：
- 如果当前节点 cur 没有左子节点，直接打印当前节点 cur 的值
- 如果 pre 节点的右指针不为空，也打印当前节点 cur 的值。
这个第一条和前序遍历的一样，都是左子节点为空的时候打印 cur 的值。这个第二条是 pre 的右指针不为空的时候打印 cur 的值，我们来看下代码。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> inorderList = new ArrayList<>();
TreeNode cur = root;// 记录当前访问的节点。
while (cur != null) {
if (cur.left == null) {
inorderList.add(cur.val);// 1，没有左子节点打印。
cur = cur.right;
} else {
TreeNode pre = cur.left;
while (pre.right != null && pre.right != cur)
pre = pre.right;
if (pre.right == null) {// 第一次到当前节点。
pre.right = cur;
cur = cur.left;
} else {// 第二次到当前节点。
inorderList.add(cur.val);// 2，pre节点的右指针不为空。
pre.right = null;
cur = cur.right;
}
}
}
return inorderList;
}
我们看到前序遍历和中序遍历只有一行代码的位置不同。我们先来消化一下前面讲的，如下图所示。
上面就是 Morris 的前序和中续遍历，而对于后序遍历稍微要复杂一些。关于前面讲的，如果没有左子节点，打印完当前节点之后直接跳到他的右子节点了，如果有左子节点，打印完当前节点和左子节点也跳到右子节点了，而后序遍历的顺序是：左子树->右子树->根节点，所以我们没法在打印完两个子节点之后在回来打印当前节点。
我们再来观察一下后序遍历的顺序，如下图所示，最先打印的是节点 4 ，这个是节点 2 的左子节点，接着打印的是节点 [5，2]，这个是节点 1 的左子节点往右走的逆序 …… ，所以我们发现如果当前节点没有左子节点不需要打印，如果有左子节点，直接打印左子节点一直往右走的逆序就行了。通过上面 Morris 的前序和中序遍历我们知道，如果当前节点有左子节点，当前节点会被访问两次，那么这里是在第一次访问的时候打印还是在第二次访问的时候打印呢？通过下图我们可以发现是在第二次访问的时候打印。这里要注意因为节点 1 是根节点，他没有父节点，所以最右侧的不会被打印到，所以在最后的时候要单独打印。
对于后序遍历就是：
- 如果当前节点 cur 没有左子节点，不用管。
- 如果当前节点 cur 有左子节点，需要在第二次访问 cur 的时候打印”左子节点一直往右走的逆序”。
- 最后根节点往右的逆序要单独打印。
最后再来看下代码。
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> posList = new ArrayList<>();
TreeNode cur = root;// 记录当前访问的节点。
while (cur != null) {
if (cur.left == null) {// 左子节点为空不用管。
cur = cur.right;
} else {
TreeNode pre = cur.left;
while (pre.right != null && pre.right != cur)
pre = pre.right;
if (pre.right == null) {// 第一次到当前节点。
pre.right = cur;
cur = cur.left;
} else {// 第二次到当前节点。
pre.right = null;
// 1，当前节点第二次访问的时候逆序打印。
printList(cur.left, posList);
cur = cur.right;
}
}
}
// 2，根节点往右的逆序要单独打印。
printList(root, posList);
return posList;
}
// 逆序打印
private void printList(TreeNode node, List<Integer> posList) {
// 这里并不是直接逆序打印，而是在打印的时候往前插入，
// 比如要逆序打印1，2，3。首先打印 1 ，结果是[1]。
// 在打印 2，打印的时候往前插入，结果是[2，1]
// 接着打印 3，打印的时候往前插入，结果是[3，2，1]
int size = posList.size();
while (node != null) {// 这里面是插入。
posList.add(size, node.val);
node = node.right;
}
}
