public class InorderThreadedBinaryTree {
    private ThreadTreeNode pre = null;
    public void threadedNodes(ThreadTreeNode node) {
        //如果node==null，不能線索化
        if (node == null) {
            return;
        }
        //1、先線索化左子樹
        threadedNodes(node.left);
        //2、線索化當(dāng)前結(jié)點(diǎn)
        //處理當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
        //以8為例來(lái)理解
        //8結(jié)點(diǎn)的.left = null，8結(jié)點(diǎn)的.leftType = 1
        if (node.left == null) {
            //讓當(dāng)前結(jié)點(diǎn)的左指針指向前驅(qū)結(jié)點(diǎn)
            node.left = pre;
            //修改當(dāng)前結(jié)點(diǎn)的左指針的類型，指向前驅(qū)結(jié)點(diǎn)
            node.leftType = 1;
        }
        //處理后繼結(jié)點(diǎn)
        if (pre != null && pre.right == null) {
            //讓當(dāng)前結(jié)點(diǎn)的右指針指向當(dāng)前結(jié)點(diǎn)
            pre.right = node;
            //修改當(dāng)前結(jié)點(diǎn)的右指針的類型=
            pre.rightType = 1;
        }
        //每處理一個(gè)結(jié)點(diǎn)后，讓當(dāng)前結(jié)點(diǎn)是下一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
        pre = node;
        //3、線索化右子樹
        threadedNodes(node.right);
    }
}
class ThreadTreeNode {
    int val;
    ThreadTreeNode left;
    //0為非線索化,1為線索化
    int leftType;
    ThreadTreeNode right;
    //0為非線索化,1為線索化
    int rightType;
    public ThreadTreeNode(int val) {
        this.val = val;
    }
}

public class Morris {
    /**
     * 將當(dāng)前根結(jié)點(diǎn)中序遍歷的結(jié)果存儲(chǔ)到list集合中
     * @param root  根結(jié)點(diǎn)
     * @return  中序遍歷的結(jié)合
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) { // 左子樹為空，則輸出當(dāng)前節(jié)點(diǎn)，然后遍歷右子樹
                res.add(curr.val);  //如果要求直接打印,直接輸出System.out.println(curr.val);
                curr = curr.right;
            } else {
                // 找到當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
                TreeNode prev = curr.left;
                while (prev.right != null && prev.right != curr) {
                    prev = prev.right;
                }
                if (prev.right == null) {
                    // 將前驅(qū)節(jié)點(diǎn)的右子樹連接到當(dāng)前節(jié)點(diǎn)
                    prev.right = curr;
                    curr = curr.left;
                } else {
                    // 前驅(qū)節(jié)點(diǎn)的右子樹已經(jīng)連接到當(dāng)前節(jié)點(diǎn)，斷開連接，輸出當(dāng)前節(jié)點(diǎn)，然后遍歷右子樹
                    prev.right = null;
                    res.add(curr.val);//如果要求直接打印,直接輸出System.out.println(curr.val);
                    curr = curr.right;
                }
            }
        }
        return res;
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) { // 左子樹為空，則輸出當(dāng)前節(jié)點(diǎn)，然后遍歷右子樹
                res.add(curr.val);//如果要求直接打印,直接輸出System.out.println(curr.val);
                curr = curr.right;
            } else {
                // 找到當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
                TreeNode prev = curr.left;
                while (prev.right != null && prev.right != curr) {
                    prev = prev.right;
                }
                if (prev.right == null) {
                    res.add(curr.val);//如果要求直接打印,直接輸出System.out.println(curr.val);
                    // 將前驅(qū)節(jié)點(diǎn)的右子樹連接到當(dāng)前節(jié)點(diǎn)
                    prev.right = curr;
                    curr = curr.left;
                } else {
                    // 前驅(qū)節(jié)點(diǎn)的右子樹已經(jīng)連接到當(dāng)前節(jié)點(diǎn)，斷開連接，輸出當(dāng)前節(jié)點(diǎn)，然后遍歷右子樹
                    prev.right = null;
                    curr = curr.right;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(5);
        root.left.right.right = new TreeNode(7);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.left.left = new TreeNode(6);
        System.out.println(preorderTraversal(root));
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode dump = new TreeNode(0);//建立一個(gè)臨時(shí)結(jié)點(diǎn)
        dump.left = root;  //設(shè)置dump的左節(jié)點(diǎn)為root
        TreeNode curr = dump;  //當(dāng)前節(jié)點(diǎn)為dump
        while (curr != null) {
            if (curr.left == null) { // 左子樹為空，則輸出當(dāng)前節(jié)點(diǎn)，然后遍歷右子樹
                curr = curr.right;
            } else {
                // 找到當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
                TreeNode prev = curr.left;
                while (prev.right != null && prev.right != curr) {
                    prev = prev.right;
                }
                if (prev.right == null) {
                    // 將前驅(qū)節(jié)點(diǎn)的右子樹連接到當(dāng)前節(jié)點(diǎn)
                    prev.right = curr;
                    curr = curr.left;
                } else {
                    reverseAddNodes(curr.left, prev, res);
                    // 前驅(qū)節(jié)點(diǎn)的右子樹已經(jīng)連接到當(dāng)前節(jié)點(diǎn)，斷開連接，輸出當(dāng)前節(jié)點(diǎn)，然后遍歷右子樹
                    prev.right = null;
                    curr = curr.right;
                }
            }
        }
        return res;
    }
    private void reverseAddNodes(TreeNode begin, TreeNode end, List<Integer> res) {
        reverseNodes(begin, end); //將begin到end的進(jìn)行逆序連接
        TreeNode curr = end;
        while (true) {//將逆序連接后端begin到end添加
            res.add(curr.val);
            if (curr == begin)
                break;
            curr = curr.right;
        }
        reverseNodes(end, begin);//恢復(fù)之前的連接狀態(tài)
    }
    /**
     * 將begin到end的進(jìn)行逆序連接
     *
     * @param begin
     * @param end
     */
    private void reverseNodes(TreeNode begin, TreeNode end) {
        TreeNode prev = begin;
        TreeNode curr = prev.right;
        TreeNode post;
        while (prev != end) {
            post = curr.right;
            curr.right = prev;
            prev = curr;
            curr = post;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(5);
        root.left.right.right = new TreeNode(7);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.left.left = new TreeNode(6);
        System.out.println(postorderTraversal(root));
    }