上图Morris序：1，2，4，2，5，1，3，6，3，7

没有左树的节点只能到一次，有左树的节点能到两次，Morris遍历可以知道是第几次到达的当前节点（通过左树的最右节点的指针）

public void morris(Node head){
    if(head==null){
        return;
    Node cur=head;
    Node mostRight=null;
    while(cur!=null){//情况三作为退出循环的条件
        mostRight=cur.left;
        if(mostRight!=null){//cur有左孩子
            while(mostRight.right!=null&&mostRight.right!=cur){//别忘了后面这个判断条件
                mostRight=mostRight.right;
            //此时mostRight是cur左子树上的最右节点
            if(mostRight.right==null){
                mostRight.right=cur;
                cur=cur.left;
                continue;
            }else{//mostRight.right=cur
                mostRight.right=null;
        cur=cur.right;
 
额外空间复杂度显然是O(1)
 
 
时间复杂度：
 keypoint：所有节点遍历左子树右边界的总代价，所有节点遍历左子树的右边界不会重复，总代价O(N)
 
 
如何将Morris序改成先序？
 
 
如果一个节点只能到达一次，就直接打印（没有左子树）
 
 
如果一个节点能到达两次，第一次打印（有左子树）
 
public void morrisPre(Node head){
    if(head==null){
        return;
    Node cur=head;
    Node mostRight=null;
    while(cur!=null){
        mostRight=cur.left;
        if(mostRight!=null){
            while(mostRight.right!=null&&mostRight.right!=cur){
                mostRight=mostRight.right;
            if(mostRight.right==null){//第一次来到cur
                System.out.println(cur.value);
                mostRight.right=cur;
                cur=cur.left;
                continue;
            }else{
                mostRight.right=null;
        }else{//没有左子树的情况
            System.out.println(cur.value);
        cur=cur.right;
 
中序遍历：
 如果一个节点只能到达一次，直接打印（没有左树）
 
 
如果一个节点能到达两次，第二次来到的时候打印（有左树）
 
public void morrisIn(Node head){
    if(head==null){
        return;
    Node cur=head;
    Node mostRight=null;
    while(cur!=null){
        mostRight=cur.left;
        if(mostRight!=null){
            while(mostRight.right!=null&&mostRight.right!=cur){
                mostRight=mostRight.right;
            if(mostRight.right==null){
                mostRight.right=cur;
                cur=cur.left;
                continue;
            }else{
                mostRight.right==null;
        System.out.println(cur.value);//优化过
        cur=cur.right;
 
当一个节点来到第二次的时候，逆序打印当前节点左树右边界
 
 
整个过程都进行完之后：单独逆序打印整棵树的右边界
 
 
如何做到逆序打印左树右边界，并且时间复杂度为O(N)，空间复杂度为O(1)
 
 
单链表的逆序操作+复原
 
public void morrisPos(Node head){
    if(head==null){
        return;
    Node cur=head;
    Node mostRight=null;
    while(cur!=null){
        mostRight=cur.left;
        if(mostRight!=null){
            while(mostRight.right!=null&&mostRight.right!=cur){
                mostRight=mostRight.right;
            if(mostRight.right==null){
                mostRight.right=cur;
                cur=cur.left;
                continue;
            }else{
                mostRight.right=null;
                printEdge(cur.left);
        cur=cur.right;
    //最后打印整颗d
    printEdge(head);
public void printEdge(Node x){
    Node tail=reverseEdge(x);
    Node cur=tail;
    while(cur!=null){
        System.out.print(cur.value+" ");
        cur=cur.right;
    reverseEdge(tail);
public Node reverseEdge(Node from){
    Node pre=null;
    Node next=null;
    while(from!=null){
        next=from.right;
        from.right=pre;
        pre=from;
        from=next;
    return pre;
				
后序遍历
对于两次到达的节点，在第二次到达的时候，逆序打印左子树右边界这一条链，只到达一次的节点不用管，最后逆序打印整棵树的右边界这条链。
逆序打印链的时候相当于单链表的逆序输出，需要改指针方向，打印之后还需要改回来，由于代码太长，这里只提供思路，详细内容请学习左程云算法进阶班课程。
#include<bits/stdc++.h>
using namespace std;
struct...
				
Morris遍历二叉树是遍历二叉树的神级方法，它的时间复杂度仅为O(n)，空间复杂度为O(1)。
主要包含以下两大步骤：
1、拿到一个节点，如果该节点无左子树，那么节点指向它的右节点。
2、如果这个节点有左子树，找到左子树的最右节点。
       a、如果最右节点指向null，则让最右节点指向当前节点，并将该目标节点向左孩子移动。
       b、如果最右节点已经指向该节点，则让最右
一种遍历二叉树的方式，并且时间复杂度O(N)，额外空间复杂度O(1)。通过利用原树中大量空闲指针的方式，达到节省空间的目的。
Morris遍历的关键
利用一棵树上大量的右指针空闲空间
Morris遍历细节
假设来到当前节点cur，开始时cur来到头节点位置
如果cur没有左孩子，cur向右移动(cur = cur.right)
如果cur有左孩子，找到左子树上最右的节点mostRight :
a. 如果mostRight的右指针指向空，让其指向cur，然后cur向左移动(cur =
				
文章目录二叉树遍历-线索二叉树（Morris）1、前序遍历-线索二叉树2、中序遍历-线索二叉树（常用）3、后序遍历-线索二叉树（不推荐）实验源码：
二叉树遍历-线索二叉树（Morris）
https://www.bilibili.com/video/BV1Jv411A7Ty?p=31
1、前序遍历-线索二叉树
https://www.bilibili.com/video/BV1Jv411A7Ty?p=32
 //1、前序-线索二叉树：根   左  右
    public static void morr
 当前节点：cur,  出发点：cur=head（头节点出发）
 1.当cur无左树，cur = cur.right （来到右子节点）
 2.当cur有左树，找左树最右节点mostright
   1）.若mostright的右指针指向null，mostright.right = cur（让左树最右节点mostright的右指针指向当前节点），cur=cur.left （当前节点来到左节点）
   2）.若mostright
1. 如果当前节点的左子节点为空时，输出当前节点，并将当前节点置为该节点的右子节点；
2. 如果当前节点的左子节点不为空，找到当前节点左子树的最右节点（该节点为当前节点中序遍历的前驱节点）；
 2.1. 如果最右节点的右指针为空(right=null)，将最右节点的右指针指向当前节点，当前节点置为其左子节点；
 2.2. 如果最右节点的右指针不为空，将最右节点右指...
				
通常，实现二叉树的前序（preorder）、中序（inorder）、后序（postorder）遍历有两个常用的方法：一是递归(recursive)，二是使用栈实现的迭代版本(stack+iterative)。这两种方法都是O(n)的空间复杂度（递归本身占用stack空间或者用户自定义的stack），所以不满足要求。Morris
 Traversal方法可以做到这两点，与前两种方法的不同在于该方法
public class Learn {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(1);
        root.left.right = ne
            // 如果当前节点有左子树，则找到左子树的最右节点
            TreeNode* pre = cur->left;
            while (pre->right != nullptr && pre->right != cur) {
                pre = pre->right;
            if (pre->right == nullptr) {
                // 如果最右节点的右子树为空，则将其指向当前节点
                pre->right = cur;
                cur = cur->left;
            } else {
                // 如果最右节点的右子树指向当前节点，则说明左子树已经遍历完毕，可以访问当前节点
                pre->right = nullptr;
                cout << cur->val << " ";
                cur = cur->right;