二叉树的前序中序后序遍历--使用递归还有栈

class BTree {

    Node root;

    public BTree() {
        Node l3left = new Node(2, null, null);
        Node l3right = new Node(3, null, null);
        Node l2left = new Node(4, l3left, l3right);
        Node l2right = new Node(5, null, null);
        root = new Node(6, l2left, l2right);
    }


    public void prevT(Node node) {
        if (node == null) {
            return;
        }
        //父节点
        System.out.println(node);
        //左节点
        prevT(node.left);
        //右节点
        prevT(node.right);

    }

    public void prevTUseStack(Node root) {
        Stack<Node> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            // 若栈非空输出root，出栈
            Node node = stack.pop();
            System.out.println(node);
            // 右节点压栈，若存在
            if (node.right != null) {
                stack.push(node.right);
            }
            //左节点压栈，若存在
            if (node.left != null) {
                stack.push(node.left);
            }
            //重复1
        }
    }

    public void inorderTraverse(Node root) {
        if (root == null) {
            return;
        }
        inorderTraverse(root.left);
        System.out.println(root);
        inorderTraverse(root.right);
    }

    public void inorderTraverseUseStack(Node root) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {

            // 如果栈顶元素非空且左节点存在，
            // 将其入栈，重复该过程。
            // 若不存在则进入第2步
            while (stack.peek().left != null) {
                stack.push(stack.peek().left);
            }
            // 若栈非空，输出栈顶元素并出栈。
            // 判断刚出栈的元素的右节点是否存在，不存在重复第2步，
            // 存在则将右节点入栈，跳至第1步
            while (!stack.isEmpty()) {
                Node node = stack.pop();
                System.out.println(node);

                if (node.right != null) {
                    stack.push(node.right);
                    break;
                }
            }
        }
    }

    public void rearTraver(Node root) {
        if (root == null) {
            return;
        }
        rearTraver(root.left);
        rearTraver(root.right);
        System.out.println(root);
    }

    public void rearTraverUseStack(Node root) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        // 需要增加一个节点记录，用于记录上次出栈的节点
        Node lastNode = null;

        while (!stack.isEmpty()) {
            // 如果栈顶元素非空且左节点存在，将其入栈，重复该过程。
            // 若不存在则进入第2步
            while (stack.peek().left != null) {
                stack.push(stack.peek().left);
            }

            // 判断上一次出栈节点是否当前节点的右节点，
            // 或者当前节点是否存在右节点，
            // 满足任一条件，将当前节点输出，并出栈。
            // 否则将右节点压栈。跳至第1步
            while (!stack.isEmpty()) {
                if (lastNode == stack.peek().right || stack.peek().right == null) {
                    Node node = stack.pop();
                    System.out.println(node);
                    lastNode = node;
                } else if (stack.peek().right != null) {
                    stack.push(stack.peek().right);
                    break;
                }
            }
        }
    }


    static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }


}