JavaMorris遍历算法及其在二叉树中的应用

public class InorderThreadedBinaryTree {
    private ThreadTreenode pre = null;
    public void threadedNodes(ThreadTreeNode node) {
        //如果node==null，不能线索化
        if (node == null) {
            return;
        }
        //1、先线索化左子树
        threadedNodes(node.left);
        //2、线索化当前结点
        //处理当前结点的前驱结点
        //以8为例来理解
        //8结点的.left = null，8结点的.leftType = 1
        if (node.left == null) {
            //让当前结点的左指针指向前驱结点
            node.left = pre;
            //修改当前结点的左指针的类型，指向前驱结点
            node.leftType = 1;
        }
        //处理后继结点
        if (pre != null && pre.right == null) {
            //让当前结点的右指针指向当前结点
            pre.right = node;
            //修改当前结点的右指针的类型=
            pre.rightType = 1;
        }
        //每处理一个结点后，让当前结点是下一个结点的前驱结点
        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 {
    
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) { // 左子树为空，则输出当前节点，然后遍历右子树
                res.add(curr.val);  //如果要求直接打印,直接输出System.out.println(curr.val);
                curr = curr.right;
            } else {
                // 找到当前节点的前驱节点
                TreeNode prev = curr.left;
                while (prev.right != null && prev.right != curr) {
                    prev = prev.right;
                }
                if (prev.right == null) {
                    // 将前驱节点的右子树连接到当前节点
                    prev.right = curr;
                    curr = curr.left;
                } else {
                    // 前驱节点的右子树已经连接到当前节点，断开连接，输出当前节点，然后遍历右子树
                    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) { // 左子树为空，则输出当前节点，然后遍历右子树
                res.add(curr.val);//如果要求直接打印,直接输出System.out.println(curr.val);
                curr = curr.right;
            } else {
                // 找到当前节点的前驱节点
                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);
                    // 将前驱节点的右子树连接到当前节点
                    prev.right = curr;
                    curr = curr.left;
                } else {
                    // 前驱节点的右子树已经连接到当前节点，断开连接，输出当前节点，然后遍历右子树
                    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);//建立一个临时结点
        dump.left = root;  //设置dump的左节点为root
        TreeNode curr = dump;  //当前节点为dump
        while (curr != null) {
            if (curr.left == null) { // 左子树为空，则输出当前节点，然后遍历右子树
                curr = curr.right;
            } else {
                // 找到当前节点的前驱节点
                TreeNode prev = curr.left;
                while (prev.right != null && prev.right != curr) {
                    prev = prev.right;
                }
                if (prev.right == null) {
                    // 将前驱节点的右子树连接到当前节点
                    prev.right = curr;
                    curr = curr.left;
                } else {
                    reverseAddNodes(curr.left, prev, res);
                    // 前驱节点的右子树已经连接到当前节点，断开连接，输出当前节点，然后遍历右子树
                    prev.right = null;
                    curr = curr.right;
                }
            }
        }
        return res;
    }
    private void reverseAddNodes(TreeNode begin, TreeNode end, List<Integer> res) {
        reverseNodes(begin, end); //将begin到end的进行逆序连接
        TreeNode curr = end;
        while (true) {//将逆序连接后端begin到end添加
            res.add(curr.val);
            if (curr == begin)
                break;
            curr = curr.right;
        }
        reverseNodes(end, begin);//恢复之前的连接状态
    }
    
    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));
    }