遍历二叉树的神级方法

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;
    }
}