定义

二叉树的 dfs

dfs（Depth-First-Search），即深度优先遍历。从根开始，一路往下遍历，遍历到底再返回，找到下一未访问的点，继续往下遍历，直到所有点都遍历完毕。如果是先访问左孩子的话，和前序遍历是一样的。

例如有一棵二叉树如下：

那么其深度优先遍历的结果为：

[1, 3, 7, 8, 11, 12, 5, 9, 15, 13, 14]

二叉树的 bfs

bfs（Breadth-First-Search），即广度优先遍历。从根开始，一层一层地往下遍历，每一层从左往右遍历，直到遍历完所有的点。也称为层序遍历。

继续用上面那个例子，二叉树如下：

其广度优先遍历为：

[1, 3, 5, 7, 8, 9, 15, 11, 12, 13, 14]

代码实现

结构定义

首先定义二叉树：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

遍历结果存储在一个 list 中：

1	private List<Integer> res = new ArrayList<>();

二叉树的 dfs

二叉树的 dfs 可分为递归实现和非递归实现。

首先看递归实现，递归实现比较简单，过程和前序遍历一样，先访问根节点，然后分别递归访问左子树和右子树：

/**
 * 深度优先遍历（递归）
 */
private void dfs_recursion(TreeNode root) {
    if (root == null) {
        return;
    }
    res.add(root.val);

    //递归遍历左子树和右子树
    dfs_recursion(root.left);
    dfs_recursion(root.right);
}

接着看非递归实现，非递归的话需要借助栈，栈用来存右子树，当没有左子树可访问的时候，就从栈中取出最近放入的右子树，具体实现如下：

/**
 * 深度优先遍历（非递归）
 */
private void dfs(TreeNode root) {
    // 栈用来存储右孩子
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null) {
        res.add(curr.val);
        if (curr.right != null) {
            stack.push(curr.right);
        }
        curr = curr.left;
        if (curr == null && !stack.isEmpty()) {
            curr = stack.pop();
        }
    }
}

二叉树的 bfs

二叉树的 bfs 同样可以分为递归和非递归两种实现。和 dfs 相反，bfs 的非递归更容易实现，所以先看非递归。

非递归需要借助队列，利用队列先进先出的性质可以很方便地一层一层遍历元素，实现如下：

/**
 * 广度优先遍历（非递归）
 */
private void bfs(TreeNode root) {
    // 利用队列先进先出的性质存储节点
    LinkedList<TreeNode> queue = new LinkedList<>();
    if (root != null) {
        queue.add(root);
    }
    while (!queue.isEmpty()) {
        TreeNode curr = queue.remove();
        res.add(curr.val);
        if (curr.left != null) {
            queue.add(curr.left);
        }
        if (curr.right != null) {
            queue.add(curr.right);
        }
    }
}

如果要递归实现的话，要每一层都用一个 list 来记录元素。具体实现如下：

/**
 * 广度优先遍历（递归）
 */
private void bfs_recursion(TreeNode root) {
    // 每一层都要借助一个 List 存储元素
    List<List<Integer>> bfsRes = new ArrayList<>();
    find(bfsRes, 0, root);
    for (int i = 0; i < bfsRes.size(); i++) {
        List<Integer> curr = bfsRes.get(i);
        res.addAll(curr);
    }
}

/**
 * 将第 level 层的 node 节点放入 res 的第 level 个集合中
 */
private void find(List<List<Integer>> res, int level, TreeNode node) {
    if (node == null) {
        return;
    }
    if (res.size() <= level) {
        List<Integer> list = new ArrayList<>();
        list.add(node.val);
        res.add(list);
    } else {
        List<Integer> list = res.get(level);
        list.add(node.val);
    }

    find(res, level+1, node.left);
    find(res, level+1, node.right);
}

参考

二叉树的DFS/BFS的递归/非递归形式