/**
 * 下文中用到的TreeNode類
 */
 class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
 }

	/**
     * 先序遍歷的原則是：先根、再左、再右。
     * @param root
     * @param list
     */
    private void preorder(TreeNode root, List<Integer> list){
        if(root != null){
            list.add(root.val);
            preorder(root.left,list);
            preorder(root.right,list);
        }
    }

    /**
     * 中序遍歷的原則是：先左、再根、再右
     * @param root
     * @param list
     */
    private void inorder(TreeNode root, List<Integer> list){
        if(root != null){
            inorder(root.left,list);
            list.add(root.val);
            inorder(root.right,list);
        }
    }

    /**
     * 后序遍歷的原則是：先左、再右、再根
     * @param root
     * @param list
     */
    private void postorder(TreeNode root, List<Integer> list){
        if(root != null){
            postorder(root.left,list);
            postorder(root.right,list);
            list.add(root.val);
        }
    }

    /**
     * 先序遍歷的原則是：先根、再左、再右。
     * 1.輔助變量 tempNode 初始化為根節(jié)點(diǎn)
     * 2.當(dāng) tempNode != null 時(shí)，就保存這個(gè)節(jié)點(diǎn)值到 list 中，然后將其入棧并置 tempNode為它自己的左子節(jié)點(diǎn)
     * 3.當(dāng) tempNode == null 時(shí)，說明已經(jīng)遍歷到二叉樹的左下節(jié)點(diǎn)了，這時(shí)前序遍歷應(yīng)該遍歷右子樹了，首先 pop 出已經(jīng)遍歷保存過的父節(jié)點(diǎn)，然后置 tempNode 為 pop 出的父節(jié)點(diǎn)的右子節(jié)點(diǎn)
     * @param root
     * @param list
     */
    private void preorder(TreeNode root, List<Integer> list){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tempNode = root;
        while(!stack.isEmpty() || tempNode != null){
            if (tempNode != null) {
                list.add(tempNode.val);
                stack.push(tempNode);
                tempNode = tempNode.left;
            } else {
                tempNode = stack.pop();
                tempNode = tempNode.right;
            }
        }
    }

    /**
     * 中序遍歷的原則是：先左、再根、再右
     * 1.輔助變量 tempNode 初始化 root
     * 3.當(dāng)棧非空或 tempNode 非 null 時(shí)，循環(huán)
     *  3.1 tempNode != null 時(shí)，說明還有左子節(jié)點(diǎn)存在，將 tempNode 入棧，并且將 tempNode 置為它自己的左子節(jié)點(diǎn)
     *  （和前序遍歷的區(qū)別在于這里遍歷到先不保存到 list 中，出棧的時(shí)候再將其保存到 list 中）
     *  3.2 tempNode == null 時(shí)，說明到二叉樹左下的節(jié)點(diǎn)了，這時(shí)棧頂?shù)母腹?jié)點(diǎn)出棧賦值給 tempNode ，并保存節(jié)點(diǎn)值到 list ，將 tempNode 置為棧頂節(jié)點(diǎn)的右子節(jié)點(diǎn)繼續(xù)循環(huán)
     * @param root
     * @param list
     */
    private void inorder(TreeNode root, List<Integer> list){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tempNode = root;
        while(!stack.isEmpty() || tempNode != null){
            if (tempNode != null) {
                stack.push(tempNode);
                tempNode = tempNode.left;
            } else {
                tempNode = stack.pop();
                list.add(tempNode.val);
                tempNode = tempNode.right;
            }
        }
    }

    /**
     * 后序遍歷的原則是：先左、再右、再根
     * 1.對(duì)應(yīng)前序遍歷的反操作：
     * 2.前序遍歷從尾部添加元素，后序遍歷從頭部添加元素
     * 3.前序遍歷去左子樹，后序遍歷去右子樹
     * @param root
     * @param list
     */
    private void postorder(TreeNode root, List<Integer> list){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tempNode = root;
        while (!stack.isEmpty() || tempNode != null) {
            if (tempNode != null) {
                stack.push(tempNode);
                list.add(0, tempNode.val);
                tempNode = tempNode.right;
            } else {
                tempNode = stack.pop();
                tempNode = tempNode.left;
            }
        }
    }