二叉树遍历(递归和非递归)前序、中序、后序遍历

    public static void recursionBefore(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.getValue() + "->");
        recursionBefore(root.getLeft());
        recursionBefore(root.getRight());
    }

    public static List beforeTree(TreeNode root){
        if (root == null) {
            return null;
        }
        List result = new ArrayList<>();
        Stack stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                if (node != null) {
                    result.add(node.getValue());
                }
                stack.push(node);
                node = node.getLeft();

            } else {
                TreeNode tem = stack.pop();
                node = tem.getRight();
            }
        }
        return result;
    }

    public static void recursionMiddle(TreeNode root) {
        if (root == null) {
            return;
        }
        recursionMiddle(root.getLeft());
        System.out.print(root.getValue() + "->");
        recursionMiddle(root.getRight());
    }

    public static List middleTree(TreeNode root){
        if (root == null) {
            return null;
        }
        List result = new ArrayList<>();
        Stack stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.getLeft();
            } else {
                TreeNode tem = stack.pop();
                if (tem != null) {
                    result.add(tem.getValue());
                }
                node = tem.getRight();
            }
        }
        return result;
    }

    public static void recursionAfter(TreeNode root) {
        if (root == null) {
            return;
        }
        recursionAfter(root.getLeft());
        recursionAfter(root.getRight());
        System.out.print(root.getValue() + "->");
    }

    public static void afterTree(TreeNode root) {
        TreeNode current = root;
        //把s1,linkedList作为栈使用
        linkedList s1 = new linkedList();
        //把S2，把linkedList作为栈使用
        linkedList s2 = new linkedList();
        while (current != null || !s1.isEmpty()) {
            while (current != null) {
                s1.addFirst(current);
                s2.addFirst(current);
                current = current.getRight();
            }
            if (!s1.isEmpty()) {
                current = s1.removeFirst();
                current = current.getLeft();
            }
        }
        while (!s2.isEmpty()) {
            System.out.print(s2.removeFirst().getValue() + " -> ");
        }
    }