二叉树主要有两种遍历方式：

深度优先遍历：先从树的根节点开始一直走到叶子节点遇到 null 为止，然后再根据遍历顺序往回走；

广度优先遍历：从根节点开始一层一层的遍历节点。

从深度优先遍历和广度优先遍历进一步拓展，有如下遍历方式：

深度优先遍历

• 前序遍历（递归法）
• 中序遍历（递归法）
• 后序遍历（递归法）

广度优先遍历

• 层序遍历（迭代法）

接下来讲解这四种遍历方式的公式模板

对于深度优先遍历的三种方式而言，最核心的就是递归如何写。写递归要注意三要素：

• 确定递归函数的传入参数和返回值
• 确定终止条件
• 确定单层递归逻辑

深度优先遍历递归模板如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        traversal(root, result);
        return result;
    }
    
    // 确定递归传入参数和返回值类型
    public void traversal(TreeNode root, List<Integer> result) {
        // 确定递归终止条件
        if (root == null) {
            return;
        }
        // 确定递归单层逻辑
        result.add(root.val);          // 中
        traversal(root.left, result);  // 左
        traversal(root.right, result); // 右
    }
}

上述模板在 “确定递归单层逻辑” 这段代码中根据递归顺序不同分成前、中、后序遍历方式

        // 前序遍历 中左右
        result.add(root.val);          // 中
        traversal(root.left, result);  // 左
        traversal(root.right, result); // 右

        // 中序遍历 左中右
        traversal(root.left, result);  // 左
        result.add(root.val);          // 中
        traversal(root.right, result); // 右

        // 后序遍历 左右中
        traversal(root.left, result);  // 左
        traversal(root.right, result); // 右
        result.add(root.val);          // 中

广度优先遍历迭代模板如下：

class Solution {

    List<List<Integer>> nodeList = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        traversal(root);
        return nodeList;
    }

    public void traversal(TreeNode curr) {
        if (curr == null) {
            return;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(curr);
        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<>();
            int len = que.size();

            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if (tmpNode.left != null) {
                    que.offer(tmpNode.left);
                }
                if (tmpNode.right != null) {
                    que.offer(tmpNode.right);
                }
                len--;
            }
            nodeList.add(itemList);
        }
    }
}

层序遍历的核心思想是借用队列来实现，队列先进先出，符合一层一层遍历的逻辑。