二叉树的前中后序迭代写法

既然是迭代，肯定需要用到栈，那么如何思考3种遍历方法是怎么运用栈的呢？
前序遍历，就是先根节点，再左孩子，然后右孩子。
一开始我们把根节点放进栈里。然后就弹出来VISIT，这样确保了先访问了根节点。根据栈后进先出的特性，这时我们需要先把右孩子放进栈里，然后是左孩子。
下面是代码

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

前序遍历的思考轨迹还是比较容易。下面是中序遍历。中序遍历要求先左孩子然后是根节点。所以当根节点放进去的时候，不应该立刻出来。因为左孩子优先。那么就一路向左，一条路走到黑，左到不能左。这里有一个门槛，就是如果到左了，下面就把最左的弹出来。这个时候如果是WHILE循环，那么栈顶的左又会因为一路向左的代码，又把左孩子塞回去。那么就是个死循环。错误代码如下

while(!st.isEmpty()){
        while(st.peek().left!=null)
            st.push(st.peek().left);
        TreeNode cur = st.pop();
        res.add(cur.val);
        if(cur.right!=null) st.push(cur.right);
  }

为了避免上述情况，我们需要额外一个NODE节点，当做CUR。然后通过CUR节点，来防止使用栈顶节点来走一路向左的逻辑。下面就会产生正确代码。

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

最后我们来思考后序遍历，就是先左孩子，后右孩子，最后是根节点。那么我们还是借用中序遍历的思想，一路做到底，利用一个CUR节点。但是左到低之后，还要看有没有右孩子，如果有右孩子，还需先把右孩子处理下。如果没有，就可以访问当前节点了。不难得出如下错误代码

        while(!st.isEmpty() || cur!=null){
            while(cur != null){
                st.push(cur);
                cur = cur.left;
            }
            if(st.peek().right !=null){
                cur = st.peek().right;
            }else{
                res.add(st.pop().val);
            }
        }

这里就是把右节点放到栈里。随后出栈。随后ST.PEEK右节点又不为空了。那么这个右节点就反复进出。为了避免这种情况，我们需要引入一个lastvisit 的节点。来切断这个情况。如果右节点不为空，并且LASTVISIT 不是这个右节点。那么才去指向右节点。不然就接着POP。

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

综上我们已经说完了常规的遍历套路。可以看到前序遍历，只要一个栈。中序遍历需要一个栈和一个CUR节点。后序遍历需要一个栈，一个CUR节点，还需要一个LASTVISIT节点。

模拟系统栈的遍历方法

前序遍历

class Command {
        String cmd;
        TreeNode r;
        public Command(String c,TreeNode r){
            cmd = c;
            this.r = r;
        }
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<Command> st = new Stack<>();
        st.push(new Command("go",root));
        while(!st.isEmpty()){
            Command cmd = st.pop();
            if(cmd.r == null) continue;
            if("go".equals(cmd.cmd)){
                st.push(new Command("go",cmd.r.right));
                
                st.push(new Command("go",cmd.r.left));
                st.push(new Command("print",cmd.r));
            }else if("print".equals(cmd.cmd)){
                res.add(cmd.r.val);
            }
        }
        return res;
    }

中序遍历

class Command {
        String cmd;
        TreeNode r;
        public Command(String c,TreeNode r){
            cmd = c;
            this.r = r;
        }
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<Command> st = new Stack<>();
        st.push(new Command("go",root));
        while(!st.isEmpty()){
            Command cmd = st.pop();
            if(cmd.r == null) continue;
            if("go".equals(cmd.cmd)){
                st.push(new Command("go",cmd.r.right));
                st.push(new Command("print",cmd.r));
                st.push(new Command("go",cmd.r.left));
            }else if("print".equals(cmd.cmd)){
                res.add(cmd.r.val);
            }
        }
        return res;
    }

后序遍历

class Command {
        String cmd;
        TreeNode r;
        public Command(String c,TreeNode r){
            cmd = c;
            this.r = r;
        }
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<Command> st = new Stack<>();
        st.push(new Command("go",root));
        while(!st.isEmpty()){
            Command cmd = st.pop();
            if(cmd.r == null) continue;
            if("go".equals(cmd.cmd)){
                st.push(new Command("print",cmd.r));
                st.push(new Command("go",cmd.r.right));
                st.push(new Command("go",cmd.r.left));
                
            }else if("print".equals(cmd.cmd)){
                res.add(cmd.r.val);
            }
        }
        return res;
    }

怎么不用栈来实现二叉树的前中后序遍历

106. Construct Binary Tree from Inorder and Postorder Traversal

首先用后序的最后一个，去把中序的队列切开。然后递归。

public TreeNode buildTree(int[] inorder, int[] postorder) {
        int l = postorder.length;
        if(l==0) return null;
        int i=0;
        for(;i<inorder.length;i++){
            if(inorder[i] == postorder[l-1]) break;
        }
        TreeNode root = new TreeNode(postorder[l-1]);
        root.left = buildTree(Arrays.copyOfRange(inorder,0,i),Arrays.copyOfRange(postorder,0,i));
        root.right = buildTree(Arrays.copyOfRange(inorder,i+1,l),Arrays.copyOfRange(postorder,i,l-1));
        return root;
    }