在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
这里就我们就来看看，面试中会怎么样来考察我们有关二叉树的问题，首先我们先定义一个节点类：
后文测试所使用的节点类如下：
ps：解释 LeetCode 上那种
二叉树的遍历分为以下三种：
先序遍历：遍历顺序规则为【根左右】
中序遍历：遍历顺序规则为【左根右】
后序遍历：遍历顺序规则为【左右根】
下面以上图为例，我们通过代码实现三种基本遍历： 先序遍历：
首先是代码实现：
// 先序遍历 public void preTraverse(TreeNode root) { if (root != null) { System.out.println(root.val); preTraverse(root.left); preTraverse(root.right); } }遍历结果：ABCDEFGHK
中序遍历：首先是代码实现：
// 中序遍历 public void inTraverse(TreeNode root) { if (root != null) { inTraverse(root.left); System.out.println(root.val); inTraverse(root.right); } }遍历结果：BDCAEHGKF
后序遍历：首先是代码实现：
// 后序遍历 public void postTraverse(TreeNode root) { if (root != null) { postTraverse(root.left); postTraverse(root.right); System.out.println(root.val); } }遍历结果：DCBHKGFEA
视频一节课搞定计算机二级难题：二叉树遍历结构
二叉树的层次遍历很好理解，在这里我举个例子。首先我们先给出一棵二叉树：
层次遍历顾名思义，就是从上到下，逐层遍历，每层从左往右输出
计算结果：5 - 4 - 8 - 11 - 13 - 4 - 7 - 2 - 1
关于遍历算法，常见的有：
深度优先遍历（DFS）
广度优先遍历（BFS）
在我刷题的过程中遇到过这样一道题：
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
即 Z 字型遍历，所以这里再加上一种：
Z 字形遍历
下面我们来看看代码上的实现：
深度优先遍历（DFS）我们所学的层次遍历只有 BFS（广搜），DFS 深搜本身是用于顺序排序的非递归实现。‘用DFS’ 来解决层次遍历这种题我也是第一次见。
它的步骤可以简要概括为：
常规深度搜索，记录下当前节点所在层 level
将当前节点加入 List 中对应的层
由于是从左往右搜索，所以也是从左往右加入
最后得到一个类似下面的结构
0 -- 5
1 -- 4 -> 8
2 -- 11 -> 13 - > 4
3 -- 7 -> 2 -> 1
这种遍历方式太少见，找不到相关的视频，好在原理容易理解
// 层次遍历(DFS) public static List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } dfs(root, res, 0); return res; } private void dfs(TreeNode root, List<List<Integer>> res, int level) { if (root == null) { return; } if (level == res.size()) { res.add(new ArrayList<>()); } res.get(level).add(root.val); dfs(root.left, res, level + 1); dfs(root.right, res, level + 1); } 广度优先遍历（BFS）与 DFS 用递归去实现不同，BFS需要用队列去实现。
层次遍历的步骤是：
对于不为空的结点，先把该结点加入到队列中
从队中拿出结点，如果该结点的左右结点不为空，就分别把左右结点加入到队列中
重复以上操作直到队列为空
说白了就是：父节点入队，父节点出队列，先左子节点入队，后右子节点入队。递归遍历全部节点即可
视频二叉树的遍历算法--层次遍历算法
public List<List<Integer>> levelOrder(TreeNode root) { List result = new ArrayList(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { ArrayList<Integer> level = new ArrayList<Integer>(); int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode head = queue.poll(); level.add(head.val); if (head.left != null) { queue.offer(head.left); } if (head.right != null) { queue.offer(head.right); } } result.add(level); } return result; } Z 字形遍历这个题型也很罕见，源于 LeetCode 上一道面试原题：