深度和广度遍历

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);
}