关于二叉树的遍历，使用栈递归或者仿栈循环都是需要O(N)的空间，Morris Traversal保证了空间为O(1)，时间还是O(N)（比原来多了一遍）。这里只介绍inOrder顺序。思路：对每一个cur节点，优先找到一个pre节点，这个pre节点的作用是，当后续cur节点遍历 到这个位置时，可以直接通过这个pre节点返回它需要返回的位置。例如： 6 / \ 4 8 / \ 2 5上面当cur节点在6的时候，pre节点会在5，因为后面当cur节点遍历到5的时候，可以通过pre节点直接返回6当cur节点再4的时候，pre节点会在2，当后面cur到2的时候，可以直接返回4pre找到了，是通过什么返回呢，因为不能修改二叉树结构，也不能使用堆栈记录。通过mirror(镜像)，也就是说，当找到pre的时候（每个pre的右节点确保为null），在它的右节点创建一个镜像节点，这个镜像节点直接指向当前的cur节点。这个操作是不占用空间的，因为只是互相引用。例如：当上面的cur为6，pre为5，那么设置pre.right=cur，感觉上是这样： 6 / \ 4 8 / \ 2 5 \ 6 / \ 4 8 …其实并没有多出来那一块，只是5引用到6罢了 6 / ↑ \ 4 ↑ 8 / \↑ 2 5 理解了这些，那么后续就简单了，当cur遍历到pre的时候并且打印后，将pre新增的引用删除恢复原来的树便可。代码：function morrisTraversal(root){ let cur=root,pre while(cur!=null){ // 当左为空，直接打印 if(cur.left==null){ console.log(cur.val) cur=cur.right }else{ // 当左不为空，先去找 pre pre=cur.left while(pre.right!=null && pre.right!==cur){ pre=pre.right } // 建立引用，用于返回 if(pre.right==null){ pre.right=cur cur=cur.left }else{ // 删除引用 console.log(cur.val) pre.right=null cur=cur.right } } }}