二叉树前中后遍历迭代法

递归遍历只要修改递归的顺序即可

记录一下二叉树前中后遍历的迭代法

/**

     *统一一下

     *@paramroot

     *@return

     */

    //前序

    public static ListpreOrder(TreeNode root){

         List<Integer>list = newArrayList();

         Stack stack =newStack();

         TreeNode cur = root;

         while(cur!=null||!stack.isEmpty()){

             //一直往左压入栈

             while(cur!=null){

                 list.add(cur.val);

                 stack.push(cur);

                 cur = cur.left;

             }

             cur = stack.pop();

             cur = cur.right;

         }

         return list;

    }

    //中序

    public ListinorderTraversal(TreeNode root) {

        if(root == null){

            return newArrayList();

        }

        List<Integer>list = newArrayList();

        Stack stack =newStack();

        TreeNode cur = root;

        while(cur != null||!stack.isEmpty()){

            while(cur!=null){

                stack.push(cur);

                cur = cur.left;

            }

            cur = stack.pop();

            list.add(cur.val);

            cur = cur.right;

        }

        return list;

    }

    //后序遍历，非递归

    public static ListpostOrder(TreeNode root){

        Stack stack =newStack<>();

        List<Integer>list = newArrayList<>();

        TreeNode cur = root;

        TreeNode p =null;//用来记录上一节点

        while(!stack.isEmpty()|| cur != null){

            while(cur != null){

                stack.push(cur);

                cur = cur.left;

            }

            cur = stack.peek();

//            后序遍历的过程中在遍历完左子树跟右子树cur都会回到根结点。所以当前不管是从左子树还是右子树回到根结点都不应该再操作了，应该退回上层。

//            如果是从右边再返回根结点，应该回到上层。

            //主要就是判断出来的是不是右子树，是的话就可以把根节点=加入到list了

            if(cur.right== null||cur.right == p){

                list.add(cur.val);

                stack.pop();

                p = cur;

                cur =null;

            }else{

                cur = cur.right;

            }

        }

        return list;

}