1 BFS、DFS算法的定义
BFS：广度优先搜索算法，也可称为层序遍历，按照二叉树的层次进行访问，可采用队列保存每一层的节点。
DFS：深度优先搜索算法，尽可能深的搜索树的分支，当当前节点所在的边都被访问过，回溯至发现当前节点边的起始节点，一直进行至源节点可达的所有节点为止。
2 二叉树的定义
public class TreeNode{
int val;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
3 采用BFS遍历二叉树的代码实现
- 代码流程
- 1.定义二叉树；
- 2.初始化队列，root入队；
- 3.循环遍历，当队列为空时跳出
- 1.节点出队；
- 2.如果左子节点不为空，左子节点入队；
- 3.如果右子节点不为空，右子节点入队；
代码实现
public class BFSTree {
public void bfsTree(TreeNode root){
LinkedList queue = new LinkedList<>();
if (root != null) queue.add(root);
while (!queue.isEmpty()){
TreeNode node = queue.poll();
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
}
}
4 采用BFS遍历二叉树的代码实现
4.1 递归实现
树中常见的DFS可分为：先序遍历、中序遍历、后序遍历，这里使用先序遍历实现。
- 代码流程
- 1.定义二叉树
- 2.递归终止条件：越过叶子节点；
- 3.递归递推：本质是对树做先序遍历
- 1.dfs(root.left);
- 2.dfs(root.right);
代码实现
public class DFSTree{
List list = new ArrayList<>();
public void dfsTree(TreeNode root){
if (root == null) return;
list.add(root.val);
dfsTree(root.left);
dfsTree(root.s
Original: https://www.cnblogs.com/csrecord/p/16434133.html
Author: IWANNPEACE
Title: 关于二叉树BFS、DFS的总结
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/714587/
转载文章受原作者版权保护。转载请注明原作者出处！