在算法：广度优先搜索（BFS）（最短路径）中，我们提到了按照广度优先遍历的搜索方式，使用队列作为常规的搜索方式，与之相对应的为深度优先搜索（DFS）。如果说BFS对应着树结构的前中后序遍历。但是DFS相对解法较为多元一些，有些时候不得不使用递归进行求解。同时，有很多求解只是进行图的遍历，不关心是广度还是深度优先，其解都是相同的。
二叉树的基本遍历：前中后序
在这里我们暂且不讨论的基于栈而是侧重基于递归的遍历实现。
对于二叉树，最常见的遍历方式有前序(又称 先序)遍历、中序遍历、后序遍历、层次遍历。前中后序只为取得的值先后顺序不同，即递归有先后。依赖栈实现的的深度优先是前序遍历。以下是一个二叉树的前序遍历代码实现：
//public class TreeNode<T> {
// public T val;
// public TreeNode<T> left;
// public TreeNode<T> right;
// public TreeNode(T x) { val = x; }
//}
public static void main(String[] args){
TreeNode<Integer> tree = …………;
inorderTraversal(tree);
}
private static List<Integer> inorderTraversal(TreeNode<Integer> root){
List<Integer> vals = new ArrayList<>();
inorder(root, vals);
return vals;
}
private static void inorder(TreeNode<Integer> node, List<Integer> vals) {
if (node == null) return;
//前序对应根-左-右
//定义遍历行为是按顺序输出
vals.add(node.val);
inorder(node.left, vals);
inorder(node.right, vals);
//如果改成这样 左根右 就是中序遍历
//inorder(node.left, vals);
//vals.add(node.val);
//inorder(node.right, vals);
}
这种递归遍历是DFS的基础，譬如，求二叉树的最大深度（当然也可以用BFS实现）