说明

此文章记录LeetCode中前序，中序，后序迭代遍历以及层次遍历，说明并不是很多，更多的可能是方便自己回顾，如果对您有所帮助，更是欣喜。
前中后都可以进行递归编写，因此迭代遍历肯定需要借助栈来完成，因为递归的本质就是栈。层次遍历有所不同，需要队列来完成，它的实质是广度优先遍历。

递归遍历

比较简单，以前序为例，其他的仅仅改变helper中res.add的位置即可

class Solution {
    List<Integer> res = new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root!=null) helper(root);
        return res;
    }
    public List<Integer> helper(TreeNode root){
        res.add(root.val);
        if (root.left!=null) helper(root.left);
        if (root.right!=null) helper(root.right);
        return res;
    }
}

前序迭代遍历——leetcode：144

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        if (root==null) return res;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right!=null) stack.push(node.right);
            if (node.left!=null) stack.push(node.left);
        }
        return res;
    }
}

中序迭代遍历——leetcode：94

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> src = new ArrayList<>();
        while (!stack.isEmpty()||root!=null){
            if (root != null){
                stack.push(root);
                root = root.left;
            }else{
                root = stack.pop();
                src.add(root.val);
                root = root.right;
            }
        }
        return src;
    }
}

后序序迭代遍历——leetcode：145

这里需要稍稍说明一下，这里的后序遍历是由前序遍历变来的：
后序遍历中遍历的顺序是左右中，而前序的顺序是中左右，如果我们改变一下左右结点进栈的顺序，就会变成中右左（这个没有实际的意义），接着我们只要倒序便可以完成左右中，及后序遍历，其中倒序可以通过LinkedList中addFirst来完成，当然也可以通过Collections.reverse()来完成，我这里用的是addFirst；

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        //List中不可以使用addFirst，所以只能用LinkedList声明
        LinkedList<Integer> src = new LinkedList<>();
        if (root==null) return src;
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            src.addFirst(node.val);
            if (node.left!=null) stack.push(node.left);
            if (node.right!=null) stack.push(node.right);
        }
        return src;
    }
}

层次遍历——leetcode：102

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if (root==null) return res;
        queue.add(root);
        while(!queue.isEmpty()){
            LinkedList<Integer> tem = new LinkedList<>();
            for (int i=queue.size();i>0;i--){
                TreeNode node = queue.poll();
                tem.add(node.val);
                if (node.left!=null) queue.add(node.left);
                if (node.right!=null) queue.add(node.right);
            }
            res.add(tem);
        }
        return res;
    }
}