遍历二叉树的神级方法

1. 如果cur没有左孩子，cur向右移动（cur=cur.right）；
2. 如果cur有左孩子，找到左子树上的最右节点mostRight：(1) 如果mostRight的右指针指向空，先让其指向cur，然后cur向左移动（cur=cur.left）；(2) 如果mostRight的右指针指向cur，让其指向null，然后cur向右移动（cur=cur.right）。
3. cur为空时遍历停止。

1. 先序遍历：任何只能到达一次的节点在到达时直接打印，可以到达两次的节点仅在第一次到达时打印；
2. 中序遍历：任何只能到达一次的节点在到达时直接打印，可以到达两次的节点仅在第二次到达时打印；
3. 后序遍历：打印时机仅为第二次到达节点的时候，对于某个能到达两次的节点cur，第二次到达它时逆序打印它左子树的右边界。在遍历完整棵树后，在逆序打印整棵树的右边界。逆序打印右边界我们可以通过链表翻转来完成，只需要将right指针看做链表节点的next指针即可。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 构建二叉树
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        TreeNode root = new TreeNode(Integer.parseInt(params[1]));
        HashMap<Integer, TreeNode> map = new HashMap<>();
        map.put(root.val, root);
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            int val = Integer.parseInt(params[0]);
            int leftVal = Integer.parseInt(params[1]);
            int rightVal = Integer.parseInt(params[2]);
            TreeNode node = map.get(val);
            if(leftVal != 0) {
                node.left = new TreeNode(leftVal);
                map.put(leftVal, node.left);
            }
            if(rightVal != 0) {
                node.right = new TreeNode(rightVal);
                map.put(rightVal, node.right);
            }
        }
        // 三种遍历
        preOrder(root);
        inOrder(root);
        postOrder(root);
    }
    
    private static void preOrder(TreeNode root) {
        if(root == null) return;
        TreeNode cur = root;
        TreeNode 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){
                    System.out.print(cur.val + " ");
                    // 第一次到左子树的最右节点，需要将其右孩子的指向指向cur
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    // 第二次到这要回复右孩子的指针
                    mostRight.right = null;
                }
            }else{
                // 只会到一次的节点，直接打印
                System.out.print(cur.val + " ");
            }
            // 没有左子树节点直接右移
            cur = cur.right;
        }
        System.out.println();
    }
    
    private static void inOrder(TreeNode root) {
        if(root == null) return;
        TreeNode cur = root;
        TreeNode 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
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    System.out.print(cur.val + " ");
                    // 第二次到这要回复右孩子的指针
                    mostRight.right = null;
                }
            }else{
                // 只会到一次的节点，直接打印
                System.out.print(cur.val + " ");
            }
            // 没有左子树节点直接右移
            cur = cur.right;
        }
        System.out.println();
    }
    
    private static void postOrder(TreeNode root) {
        if(root == null) return;
        TreeNode cur = root;
        TreeNode 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
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    // 第二次到这要回复右孩子的指针
                    mostRight.right = null;
                    printEdge(cur.left);          // 逆序打印左树右边界
                }
            }
            // 没有左子树节点直接右移
            cur = cur.right;
        }
        // 遍历完成后还需要打印整棵树的右边界
        printEdge(root);
        System.out.println();
    }
    
    private static void printEdge(TreeNode node) {
        TreeNode tail = reverseEdge(node);
        TreeNode cur = tail;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
        // 逆序打印后还要把指针指向还原回去
        reverseEdge(tail);
    }
    
    // 翻转链表操作
    private static TreeNode reverseEdge(TreeNode cur) {
        TreeNode prev = null;
        TreeNode next = null;
        while(cur != null){
            next = cur.right;
            cur.right = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

let [n,root]=readline().split(' ').map(item=>parseInt(item))
let myMap=new Map()
while(n--){
    let [fa,lch,rch]=readline().split(' ').map(item=>parseInt(item))
    myMap.set(fa,[lch,rch])
}

const listNode=function(val){
    this.val=val
    this.left=null
    this.right=null
}

const createTree=function(root){
    if(root){
        let [lch,rch]=myMap.get(root)
        let node=new listNode(root)
        node.left=createTree(lch)
        node.right=createTree(rch)
        return node
    }
}

const treeHead=createTree(root)


let res=[]
//morris顺序
const morris=function(root){
    if(root==null)return ;
    let cur=root;
    let 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
                res.push(cur.val)
                cur=cur.left
                continue
            }else{
            //左子树的最右节点第二次被找到
            res.push(cur.val)
                mostRight.right=null
            }
        }else{
            res.push(cur.val)
        }
            cur=cur.right            
    }
}
morris(treeHead)
// console.log(res.join(' '))

 res=[]
//morris顺序 先序
const premorris=function(root){
    if(root==null)return ;
    let cur=root;
    let 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
                res.push(cur.val)
                cur=cur.left
                continue
            }else{
            //左子树的最右节点第二次被找到
                
                mostRight.right=null
            }
        } //没有左子树
        else{
            res.push(cur.val)
        }
            cur=cur.right            
        
    }
}
premorris(treeHead)
console.log(res.join(' '))
res=[]

//morris顺序 中序
const inmorris=function(root){
    if(root==null)return ;
    let cur=root;
    let 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{
            //左子树的最右节点第二次被找到
//                 res.push(cur.val)
                mostRight.right=null
            }
        }//没有左子树
            res.push(cur.val)
            cur=cur.right            
        
    }
}
inmorris(treeHead)
console.log(res.join(' '))
res=[]

const reverseedg=function(from){
    let pre=null
    let next = null
    while(from!=null){
        next=from.right
        from.right=pre
        pre=from
        from=next
    }
    return pre
}

const printegd=function(root){
    let tail=reverseedg(root)
    let cur=tail
    while(cur!=null){
        res.push(cur.val)
        cur=cur.right
    }
    //把树的链表复原
    reverseedg(tail)
}
const bemorris=function(root){
        if(root==null)return ;
    let cur=root;
    let 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
                //打印左子树的右边界
                printegd(cur.left)
            }
        }//没有左子树
          
            cur=cur.right            
        
    }
      printegd(root)
}



bemorris(treeHead)
console.log(res.join(' '))