面试被问 DFS 和 BFS 就跪了？这份图文详解你赶紧收好 ！

• 深度优先遍历，广度优先遍历简介

• 习题演练

• DFS，BFS 在搜索引擎中的应用

深度优先遍历，广度优先遍历简介

1、深度优先遍历

• 递归实现

public?class?Solution?{
????private?static?class?Node?{
????????/**
?????????*?节点值
?????????*/
????????public?int?value;
????????/**
?????????*?左节点
?????????*/
????????public?Node?left;
????????/**
?????????*?右节点
?????????*/
????????public?Node?right;

????????public?Node(int?value,?Node?left,?Node?right)?{
????????????this.value?=?value;
????????????this.left?=?left;
????????????this.right?=?right;
????????}
????}

????public?static?void?dfs(Node?treeNode)?{
????????if?(treeNode?==?null)?{
????????????return;
????????}
????????//?遍历节点
????????process(treeNode)
????????//?遍历左节点
????????dfs(treeNode.left);
????????//?遍历右节点
????????dfs(treeNode.right);
????}
}
递归的表达性很好，也很容易理解，不过如果层级过深，很容易导致栈溢出。所以我们重点看下非递归实现

• 非递归实现

1. 对于每个节点来说，先遍历当前节点，然后把右节点压栈，再压左节点（这样弹栈的时候会先拿到左节点遍历，符合深度优先遍历要求）

2. 弹栈，拿到栈顶的节点，如果节点不为空，重复步骤 1， 如果为空，结束遍历。

/**
?*?使用栈来实现?dfs
?*?@param?root
?*/
public?static?void?dfsWithStack(Node?root)?{
????if?(root?==?null)?{
????????return;
????}

????Stack<Node>?stack?=?new?Stack<>();
????//?先把根节点压栈
????stack.push(root);
????while?(!stack.isEmpty())?{
????????Node?treeNode?=?stack.pop();
????????//?遍历节点
????????process(treeNode)

????????//?先压右节点
????????if?(treeNode.right?!=?null)?{
????????????stack.push(treeNode.right);
????????}

????????//?再压左节点
????????if?(treeNode.left?!=?null)?{
????????????stack.push(treeNode.left);
????????}
????}
}
可以看到用栈实现深度优先遍历其实代码也不复杂，而且也不用担心递归那样层级过深导致的栈溢出问题。

2、广度优先遍历

/**
?*?使用队列实现?bfs
?*?@param?root
?*/
private?static?void?bfs(Node?root)?{
????if?(root?==?null)?{
????????return;
????}
????Queue<Node>?stack?=?new?LinkedList<>();
????stack.add(root);

????while?(!stack.isEmpty())?{
????????Node?node?=?stack.poll();
????????System.out.println("value?=?"?+?node.value);
????????Node?left?=?node.left;
????????if?(left?!=?null)?{
????????????stack.add(left);
????????}
????????Node?right?=?node.right;
????????if?(right?!=?null)?{
????????????stack.add(right);
????????}
????}
}

习题演练

习题演练

leetcode 104，111: 给定一个二叉树，找出其最大/最小深度。

????3
???/?\
??9??20
????/??\
???15???7
则它的最小深度  2，最大深度 3。

/**
?*?leetcode?104:?求树的最大深度
?*?@param?node
?*?@return
?*/
public?static?int?getMaxDepth(Node?node)?{
????if?(node?==?null)?{
????????return?0;
????}
????int?leftDepth?=?getMaxDepth(node.left)?+?1;
????int?rightDepth?=?getMaxDepth(node.right)?+?1;
????return?Math.max(leftDepth,?rightDepth);
}

/**
?*?leetcode?111:?求树的最小深度
?*?@param?node
?*?@return
?*/
public?static?int?getMinDepth(Node?node)?{
????if?(node?==?null)?{
????????return?0;
????}
????int?leftDepth?=?getMinDepth(node.left)?+?1;
????int?rightDepth?=?getMinDepth(node.right)?+?1;
????return?Math.min(leftDepth,?rightDepth);
}

leetcode 102: 给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。示例，给定二叉树：[3,9,20,null,null,15,7]

????3
???/?\
??9??20
????/??\
???15???7

[
??[3],
??[9,20],
??[15,7]
]

/**
?*?leetcdoe?102:?二叉树的层序遍历,?使用?bfs
?*?@param?root
?*/
private?static?List<List<Integer>>?bfsWithBinaryTreeLevelOrderTraversal(Node?root)?{
????if?(root?==?null)?{
????????//?根节点为空，说明二叉树不存在，直接返回空数组
????????return?Arrays.asList();
????}

????//?最终的层序遍历结果
????List<List<Integer>>?result?=?new?ArrayList<>();

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

????while?(!queue.isEmpty())?{
????????//?记录每一层
????????List<Integer>?level?=?new?ArrayList<>();
????????int?levelNum?=?queue.size();
????????//?遍历当前层的节点
????????for?(int?i?=?0;?i?<?levelNum;?i++)?{
????????????Node?node?=?queue.poll();
????????????//?队首节点的左右子节点入队,由于?levelNum?是在入队前算的，所以入队的左右节点并不会在当前层被遍历到
????????????if?(node.left?!=?null)?{
????????????????queue.add(node.left);
????????????}
????????????if?(node.right?!=?null)?{
????????????????queue.add(node.right);
????????????}
????????????level.add(node.value);
????????}
????????result.add(level);
????}

????return?result;
}

class?Solution:
????def?levelOrder(self,?root):
????????"""
????????:type?root:?TreeNode
????????:rtype:?List[List[int]]
????????"""
????????res?=?[]??#嵌套列表，保存最终结果
????????if?root?is?None:
????????????return?res

????????from?collections?import?deque
????????que?=?deque([root])??#队列，保存待处理的节点
????????while?len(que)!=0:
????????????lev?=?[]??#列表，保存该层的节点的值
????????????thislevel?=?len(que)??#该层节点个数
????????????while?thislevel!=0:
????????????????head?=?que.popleft()??#弹出队首节点
????????????????#队首节点的左右孩子入队
????????????????if?head.left?is?not?None:
????????????????????que.append(head.left)
????????????????if?head.right?is?not?None:
????????????????????que.append(head.right)
????????????????lev.append(head.val)??#队首节点的值压入本层
????????????????thislevel-=1
????????????res.append(lev)
????????return?res

private?static?final?List<List<Integer>>?TRAVERSAL_LIST??=?new?ArrayList<>();
/**
?*?leetcdoe?102:?二叉树的层序遍历,?使用?dfs
?*?@param?root
?*?@return
?*/
private?static?void?dfs(Node?root,?int?level)?{
????if?(root?==?null)?{
????????return;
????}

????if?(TRAVERSAL_LIST.size()?<?level?+?1)?{
????????TRAVERSAL_LIST.add(new?ArrayList<>());
????}

????List<Integer>?levelList?=?TRAVERSAL_LIST.get(level);
????levelList.add(root.value);

????//?遍历左结点
????dfs(root.left,?level?+?1);

????//?遍历右结点
????dfs(root.right,?level?+?1);
}

DFS，BFS 在搜索引擎中的应用

总结

你点的每个“在看”，我都认真当成了喜欢