非递归遍历二叉树

先序遍历

思路：用栈来存储二叉树各个节点，每走一步存储到栈中，并且存储到链表中，当节点左子树等于null，出栈岗前节点，找到出栈节点的右子树继续遍历，最后返回链表

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();//最后输出链表
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root, top;//遍历真棵树和临时记录出栈元素
        while (cur!=null || !stack.isEmpty()) {//先理解下边while循环最后写这个循环，
            //如果没有!stack.isEmpty()，那么cur走到第一个叶子节点的时候就会最终返回list
            while (cur != null) {//开始遍历的时候，一直遍历到cur等null出栈找右子树
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            top = stack.pop();//出栈找右子树
            cur = top.right;

        }
        return list;
    }

非递归先序遍历

中序遍历

思路：和前序遍历差不多，不一样的是，我们先打印左子树其次是根，所以根节点入栈时先不加入到链表中，等节点出栈在添加到链表中

 public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();//最后输出链表
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root, top;//遍历真棵树和临时记录出栈元素
        while (cur!=null || !stack.isEmpty()) {//先理解下边while循环最后写这个循环，
            //如果没有!stack.isEmpty()，那么cur走到第一个叶子节点的时候就会最终返回list
            while (cur != null) {//开始遍历的时候，一直遍历到cur等null出栈找右子树
                stack.push(cur);
                cur = cur.left;
            }
            top = stack.pop();//出栈找右子树
            list.add(top.val);弹出时在打印
            cur = top.right;

        }
        return list;
    }

后续遍历

  public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();//最后输出链表
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root, top;//遍历真棵树和临时记录出栈元素
        TreeNode pre=null;
        while (cur != null || !stack.isEmpty()) {//先理解下边while循环最后写这个循环，
            //如果没有!stack.isEmpty()，那么cur走到第一个叶子节点的时候就会最终返回list
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            top = stack.peek();//防止还有右子树，先不打印
            if (top.right == null || top.right == pre) {//pre记录被打印节点
                stack.pop();
                list.add(top.val);
                pre = top;
            }
            else {
                cur=top.right;//还有右子树
            }
        }
        return list;
    }