一、二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历

思路分析：
定义一个cur结点去遍历左子树，每遍历一个结点就将它放入栈中并且打印，直到左子树为空时。

从栈中弹出一个元素top,cur指向top的右子树.直到cur为空并且栈也为空时便不在循环。

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }

二、二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

思路分析：
中序遍历与前序遍历思路大致相同，都是定义一个cur结点去遍历二叉树，不过中序遍历是一直将左子树放入stack中，直到左子树为空。

当左子树为空时，从stack中弹出一个结点，然后打印该节点，使cur指向top的右节点，直到cur为空并且栈也为空时便不在循环。

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            cur = top.right;
        }
        return list;
    }

三、二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

思路分析：
后序遍历同样的，遍历二叉树，将每一个结点放入stack中，直到左子树为空时。

需要注意的是我们不是直接弹出栈，而是peek一下栈顶元素，这里我们就要分情况讨论了top的右子树是否为空，如果为空直接打印top元素，并且弹出，如果不为空那么使用cur指向top的右子树。
但这样我们的程序会出现一个bug，我们使cur指向top右节点后，将cur打印弹出后。
我们会发现程序又会使cur指向top右节点，这样无止的循环。

所以我们定义一个pre变量，prev用来定义上一次打印的结点，如果top的的右节点与prev结点相同时将不再遍历右节点，而直接打印top结点，并且stack弹出元素。

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == prev) {
                list.add(top.val);
                stack.pop();
                prev = top;
            }else {
                cur = top.right;
            }
        }
        return list;
    }