非递归遍历二叉树算法

前序：

    public int[] preorderTraversal (TreeNode root) {
        ArrayList<Integer> arr = new ArrayList();
        //前后是解题平台要求；核心代码开始
        Stack<TreeNode> s = new Stack();
        TreeNode p = root;
        while(p != null || !s.isEmpty()) {
            while(p!=null) {
                arr.add(p.val);
                s.push(p);
                p=p.left;
            }
            if(!s.isEmpty()) {
                TreeNode top = s.peek();
                p = top.right;
                s.pop();
            }
        }
        //核心代码结束
        int[] ret = new int[arr.size()];
        for(int i=0; i < arr.size(); i++) {
            ret[i] = arr.get(i);
        }
        return ret;
    }

1.首先，开头不需要单独判断root是否为null，后面的代码是兼容的；当然判断了也OK，可以节省一点时间和空间。
2.核心代码部分，也可以去掉内部的while循环，改成if，如下：
循环下探左孩子，将借助外围的while循环来实现（同样是p!=null时进行循环）；而内部if不满足时，因为进入了循环，肯定满足了!s.isEmpty()，所以else内执行前实际判断了!s.isEmpty()，同样是借助了外围while中的判断。

    public int[] preorderTraversal (TreeNode root) {
        ArrayList<Integer> arr = new ArrayList();
        //前后是解题平台要求；核心代码开始
        Stack<TreeNode> s = new Stack();
        TreeNode p = root;
        while(p != null || !s.isEmpty()) {
            if(p != null) {
                arr.add(p.val);
                s.push(p);
                p=p.left;
            } else {
                TreeNode top = s.peek();
                p = top.right;
                s.pop();
            }
        }
        //核心代码结束
        int[] ret = new int[arr.size()];
        for(int i=0; i < arr.size(); i++) {
            ret[i] = arr.get(i);
        }
        return ret;
    }

中序 ==>可用于判断是否是二叉搜索树（又叫二叉排序树）

中序和前序的代码完全类似，区别仅在于：前序是在下探左孩子过程中就进行遍历访问（即先访问父节点，再访问左孩子），中序是等左孩子下探完成之后才进行遍历访问（也即先访问左孩子、再访问父节点）

    public int[] inorderTraversal (TreeNode root) {
        ArrayList<Integer> arr = new ArrayList();
        //前后是解题平台要求；核心代码开始
        Stack<TreeNode> s = new Stack();
        TreeNode p = root;
        while(p != null || !s.isEmpty()) {
            while(p!=null) {
                s.push(p);
                p=p.left;
            }
            if(!s.isEmpty()) {
                TreeNode top = s.peek();
                arr.add(top.val);
                s.pop();
                p = top.right;
            }
        }
        //核心代码结束
        int[] ret = new int[arr.size()];
        for(int i=0; i < arr.size(); i++) {
            ret[i] = arr.get(i);
        }
        return ret;
    }

同样的逻辑原因，也可以去掉内部的while循环，改成if，如下：

    public int[] inorderTraversal (TreeNode root) {
        ArrayList<Integer> arr = new ArrayList();
        //前后是解题平台要求；核心代码开始
        Stack<TreeNode> s = new Stack();
        TreeNode p = root;
        while(p != null || !s.isEmpty()) {
            if(p != null) {
                s.push(p);
                p=p.left;
            } else {
                TreeNode top = s.peek();
                arr.add(top.val);
                s.pop();
                p = top.right;
            }
        }
        //核心代码结束
        int[] ret = new int[arr.size()];
        for(int i=0; i < arr.size(); i++) {
            ret[i] = arr.get(i);
        }
        return ret;
    }

后序

后序的逻辑和前序、中序都不太一样，稍微复杂一些：

    public int[] postorderTraversal (TreeNode root) {
        if(root==null) return new int[0];
        ArrayList<Integer> arr = new ArrayList();
        //前后是解题平台要求；核心代码开始
        Stack<TreeNode> s = new Stack();
        //需要两个指针，一个指向当前尝试访问(不一定会访问)的节点，一个指向上次完成访问的节点
        TreeNode cur = null;
        TreeNode pre = null; 
        s.push(root);
        while(!s.isEmpty()) { //不再判断cur是否为null，整个过程保证非null的node才会压到栈里。只需判断栈是否为空
            cur = s.peek();
            //两个条件满足其一，即可访问
            if( (cur.left==null && cur.right==null) || //1.当前节点是叶子节点
               (pre!=null && (cur.left==pre || cur.right==pre)) ) { //2.当前节点是上次实际访问节点的父节点。注意pre要非null，保证实际发生过节点访问，因为pre初始值是null
                arr.add(cur.val);
                s.pop();
                pre = cur;
            } else {
                //前面已经先压了父节点(根节点，以及此处对于下次while循环相当于在压父节点)，这里先压右孩子，再压左孩子；
                //后进先出，这样出栈时才能保证先左后右再父，满足后序遍历规则
                if(cur.right!=null) {
                    s.push(cur.right);
                }
                if(cur.left!=null) {
                    s.push(cur.left);
                }
            }
        }
        //核心代码结束
        int[] ret = new int[arr.size()];
        for(int i=0; i < arr.size(); i++) {
            ret[i] = arr.get(i);
        }
        return ret;
    }