深度优先遍历（DFS）和广度优先遍历（BFS）是两种遍历或搜索树和图的方法，常用于，呃，面试中……

深度优先遍历（DFS：Depth First Search）

DFS的遍历顺序又分为三种。下面以N代表当前结点，L代表左侧子结点，R代表右侧子结点。

• 先序（preorder）：先处理当前结点，然后对子结点从左向右处理。NLR，从上向下，从左向右
• 中序（inorder）：先处理左侧子结点，然后处理当前结点，最后处理右侧子结点。LNR，左–>当前–>右
• 后序（postorder）：先从左向右处理子结点，然后处理当前结点。LRN，从下向上，从左向右

如果把表达式放入二叉树，那么先序遍历的结果是前缀表示法（波兰表示法，Polish Notation），中序遍历的结果是中缀表示法，后序遍历的结果是后缀表示法（逆波兰表示法，Reverse Polish Notation）。

DFS的特点天然地适合使用递归的方法实现。三种顺序仅仅通过改变处理程序片段的位置就能实现，十分简单易行。用循环来实现的话，就得自己维护一个栈，而且实现起来也比较麻烦。

private void dfsInorder(Node node) {
    if (node == null) {
       return;
    }

    // 处理左子结点
    if (node.left != null) {
        dfsInorder(node.left);
    }

    // 处理本结点
    handle(node);

    // 处理右子结点
    if (ndoe.right != null) {
        dfsInorder(node.right);
    }
}

private void dfsPreorder(Node node) {
    if (node == null) {
       return;
    }

    // 处理本结点
    handle(node);

    // 处理子结点
    if (node.left != null) {
        dfsPreorder(node.left);
    }

    if (ndoe.right != null) {
        dfsPreorder(node.right);
    }
}

private void dfsPostorder(Node node) {
    if (node == null) {
       return;
    }

    // 处理子结点
    if (node.left != null) {
        dfsPostorder(node.left);
    }

    if (ndoe.right != null) {
        dfsPostorder(node.right);
    }

    // 处理本结点
    handle(node);
}

循环的方法：估计面试时不会要求做这个吧？其中，前序比较容易，而中序比较难，后序本来更难，但鉴于它与先序的对称性，可以把结果按先序（但是改为从右向左）压入栈中，再反向逐个弹出即可。

public void dfsPreorder(Node root) {
    if (root == null) {
        return;
    }

    Deque<Node> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node node = stack.pop();
        handle(node);

        if (node.right!= null) {
            stack.push(node.right);
        }

        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

public void dfsInorder(Node root) {
    if (root == null) {
        return;
    }

    Deque<Node> stack = new ArrayDeque<>();
    Node node = root;

    while (node != null || !stack.isEmpty()) {
        if (node != null) {
            stack.push(node);
            node = node.left;
        } else {
            node = stack.pop();
            handle(node);
            node = node.right;
        }
    }
}

public void dfsPostorder(Node root) {
    if (root == null) {
        return;
    }

    Deque<Node> stack = new ArrayDeque<>();
    Deque<Node> reversedStack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node node = stack.pop();
        reversedStack.push(node);

        if (node.left != null) {
            stack.push(node.left);
        }

        if (node.right != null) {
            stack.push(node.right);
        }
    }

    while (!reversedStack.isEmpty()) {
        handle(reversedStack.pop());
    }
}

广度优先遍历（BFS：Breadth First Search）

BFS的访问顺序一般是从左向右，从上向下，一层一层地处理。一般用循环通过某种容器（queue、stack、set等）来实现。

public void bfs(Node root) {
    if (root == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        handle(node);

        if (node.left != null) {
            queue.offer(node.left);
        }

        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

有时候在做BFS时，需要在处理完每一层后，都做一些其他的处理。这种情况下，可以在while循环中再套一个循环来实现：

public void bfsPerLevel(Node root) {
    if (root == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    int count = 0;

    while (!queue.isEmpty()) {
        int n = queue.size();

        for (int i = 0; i < n; ++i) {
            Node node = queue.poll();
            handle(node);

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        // 此处加入处理完当前层后的代码
        log.info(">>> end of level {}", count++);
    }
}

一般来说，递归跟栈相关，所以对于DFS这种递归属性的算法，可以在循环中用栈来实现。而对于BFS这种跟栈没关系的算法，一般人就会认为不能用递归实现。但实际上还是有办法做到的：

private void recursiveBfsHelper(List<Node> nodeList) {
    if (nodeList.isEmpty()) {
        return;
    }

    List<Node> nextList = new ArrayList<>();

    for (Node node : nodeList) {
        handle(node);

        if (node.left != null) {
            nextList.add(node.left);
        }

        if (node.right != null) {
            nextList.add(node.right);
        }
    }

    recursiveBfsHelper(nextList);
}

public void recursiveBfs(Node root) {
    recursiveBfsHelper(Collections.singletonList(root));
}

DFS算法实现起来简短方便（用递归的话），因此十分适合在面试中使用。但有些问题则需要用到BFS，比如求迷宫最短路径问题（因为逐层扫描直到找到解为止，这个解一定是最优解（或最优解之一），这里的最优解是路径最短的意思。

例题：二叉树的序列化和反序列化

将二叉树序列化为一个字符串，并将字符串反序列化为二叉树。

• 需要产生压缩的结果，否则对于只有右子树的二叉树，结果会过长。
• 由于上述要求，用DFS比较恰当，因为产生的结果便于反序列化。

    // 序列化

    // DFS preorder
    private void dfs(TreeNode root, StringBuilder sb) {
        sb.append(",");

        if (root != null) {
            sb.append(root.val);
            dfs(root.left, sb);
            dfs(root.right, sb);
        }
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }

        StringBuilder sb = new StringBuilder(root.val);
        dfs(root.left, sb);
        dfs(root.right, sb);

        return sb.toString();
    }

    // 反序列化

    private TreeNode dfs(Queue<String> queue) {
        TreeNode root = null;

        if (!queue.isEmpty()) {
            String s = queue.poll();

            if (!s.equals("")) {
                root = new TreeNode(Integer.parseInt(s));
                root.left = dfs(queue);
                root.right = dfs(queue);
            }
        }

        return root;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }

        Queue<String> queue = Arrays.stream(data.split(",", -1)
                .collect(Collectors.toCollection(LinkedList::new));

        return dfs(queue);
    }