BFS（广度优先遍历，Breadth First Search）深度优先遍历，Depth First Search）是遍历树或图的两种最常用的方法。
定义二叉树
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
使用Queue实现广度优先遍历
public void BFSWithQueue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
if (root != null)
queue.add(root);
while (!queue.isEmpty()) {
TreeNode treeNode = queue.poll();
//在这里处理遍历到的TreeNode节点
if (treeNode.left != null)
queue.add(treeNode.left);
if (treeNode.right != null)
queue.add(treeNode.right);
}
}
使用递归实现深度优先遍历遍历二叉树：
//DFS递归实现
public void DFSWithRecursion(TreeNode root) {
if (root == null)
return;
//在这里处理遍历到的TreeNode节点
if (root.left != null)
DFSWithRecursion(root.left);
if (root.right != null)
DFSWithRecursion(root.right);
}
