144. 二叉树的前序遍历

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

1.栈，链表，队列的初始化

145. 二叉树的后序遍历

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

94. 二叉树的中序遍历

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

102. 二叉树的层序遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root==null) return res;
        Queue<TreeNode> q=new ArrayDeque<TreeNode>();
        TreeNode cur=root;
        q.offer(root);
        while(!q.isEmpty()) {
            int n=q.size();
            List<Integer> level=new ArrayList<Integer>();
            for(int i=0;i<n;i++){
                cur=q.poll();
                level.add(cur.val);
                if(cur.left!=null) q.offer(cur.left);
                if(cur.right!=null) q.offer(cur.right);
            }
            res.add(level);
        }
        return res;
    }
}

层序遍历的难点在于如何确定每层有多少个元素，每次进入while循环就是一层，所以root必须提前入队。