二叉树的后序遍历

import java.util.Stack;

public class App {

    static class TreeNode {
        TreeNode() {

        }

        private TreeNode left;
        private TreeNode right;
        private int value;

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }



    /**
     * 递归
     */
    public static void behind(TreeNode cur) {
        if (cur == null) {
            return;
        }

        if (cur.left == null && cur.right == null) {
            System.out.print(cur.value);
            return;
        }

        behind(cur.left);
        behind(cur.right);
        System.out.print(cur.value);

    }

    /**
     * 非递归
     */
    public static void behind2(TreeNode root) {
        Stack<TreeNode> result = new Stack<TreeNode>();
        Stack<TreeNode> stack = new Stack<TreeNode>();

        stack.push(root);

        TreeNode curNode;
        while (!stack.isEmpty()) {
            curNode = stack.pop();
            result.push(curNode);


            if (curNode.left != null) {
                stack.add(curNode.left);
            }

            if (curNode.right != null) {
                stack.add(curNode.right);
            }

        }

        while (!result.isEmpty()) {
            System.out.print(result.pop().value);
        }
    }

    /**
     * 非递归
     */
    private static void behind3(TreeNode node) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode pop = null;
        while (node != null || !stack.isEmpty()) {
            if (node != null && node != pop) {
                stack.push(node);
                node = node.left;
            } else {
                if (!stack.isEmpty()) {
                    node = stack.peek();
                    if (node.right == null || node.right == pop) {
                        stack.pop();
                        pop = node;
                        System.out.print(node.value);
                    } else {
                        node = node.right;
                    }
                } else {
                    node = null;
                }
            }
        }
    }




    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode();


        treeNode.value = 1;
        TreeNode left = new TreeNode();
        left.value = 2;
        TreeNode left4 = new TreeNode();
        left4.value = 4;


        left.setLeft(left4);
        TreeNode right5 = new TreeNode();
        right5.value = 5;

        left.setRight(right5);

        treeNode.setLeft(left);
        TreeNode right3 = new TreeNode();
        right3.value = 3;
        TreeNode left6 = new TreeNode();
        left6.value = 6;


        TreeNode right7 = new TreeNode();
        right7.value = 7;

        right3.setRight(right7);


        right3.setLeft(left6);
        right3.setRight(right7);


        treeNode.setRight(right3);

        behind(treeNode);
        System.out.println();
        behind2(treeNode);
        System.out.println();
        behind3(treeNode);


    }
}