算法之计算最小深度 - 算法 - 知识海洋

# 最小深度算法

说明：计算树节点的最小深度

都是要访问完全部节点的，根据访问节点的顺序与方式，可以分为广度优先算法（BFS）和深度优先算法（DFS）

TreeNode构成

	public class TreeNode {
	int data;
	int depth; // 使用广度优先的时候要这个
	TreeNode left;
	TreeNode right;
	@Override
	public String toString() {
	return "data='" + data +
	", depth=" + depth ;
	}
	public TreeNode() {
	this.left=null;
	this.right=null;
	}
	public TreeNode(int data) {
	this.data = data;
	}
	public TreeNode(int data, int depth) {
	this.data = data;
	this.depth = depth;
	}
	public TreeNode(int data, TreeNode left, TreeNode right) {
	this.data = data;
	this.left = left;
	this.right = right;
	}
	public TreeNode(int data, int depth, TreeNode left, TreeNode right) {
	this.data = data;
	this.depth = depth;
	this.left = left;
	this.right = right;
	}
	public int getData() {
	return data;
	}
	public void setData(int data) {
	this.data = data;
	}
	public int getDepth() {
	return depth;
	}
	public void setDepth(int depth) {
	this.depth = depth;
	}
	public TreeNode getLeft() {
	return left;
	}
	public void setLeft(TreeNode left) {
	this.left = left;
	}
	public TreeNode getRight() {
	return right;
	}
	public void setRight(TreeNode right) {
	this.right = right;
	}
	}

# 深度优先算法（DFS）

深度优先算法介绍

百度百科说明：深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点 (即那些不包含任何超链的 HTML 文件) 。在一个 HTML 文件中，当一个超链被选择后，被链接的 HTML 文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着 HTML 文件上的超链走到不能再深入为止，然后返回到某一个 HTML 文件，再继续选择该 HTML 文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。

深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形
1、把根节点压入栈中。

2、每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。

3、找到所要找的元素时结束程序。

4、如果遍历整个树还没有找到，结束程序。

类似于二叉树的前序遍历

自己的代码：

	static int DFSMinDepth(TreeNode root) {
	// 如果节点是否为空则返回 0
	if (root == null) return 0;
	// 判断是否有子节点
	if (root.left == null && root.right == null) return 1;
	// 设置一个最大的数字进行比较，那么不过有多少层（在 int 的范围内）都会比现在设置的值要小
	int min = Integer.MAX_VALUE;
	// 递归调用进行子节点查找
	if (root.left != null) min = Math.min(DFSMinDepth(root.left), min);
	if (root.right != null) min = Math.min(DFSMinDepth(root.right), min);
	// 这个是因为从叶子节点慢慢往上执行，所以要 + 1
	return min + 1;
	}
	// 主方法
	public static void main(String[] args) {
	TreeNode node5 = new TreeNode(5);
	TreeNode node4 = new TreeNode(4);
	TreeNode node3 = new TreeNode(3, node4, null);
	TreeNode node2 = new TreeNode(2, null, node5);
	TreeNode node1 = new TreeNode(1, node3, null);
	TreeNode root = new TreeNode(0, node1, node2);
	System.out.println(DFSMinDepth(root));
	}

控制台的说明：

	// 树的样子：
	// 0
	// / \
	// 1 2
	// / \
	// 3 5
	// /
	// 4
	// 控制台输出：3，最小深度是 3 此算法的查找执行顺序是：4->3->1->5->2->0

# 广度优先搜索（BFS)

广度优先算法介绍

百度百科：宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra 单源最短路径算法和 Prim 最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫 BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

遍历规则：

先访问完当前顶点的所有邻接点。(应该看得出广度的意思)
先访问顶点的邻接点先于后访问顶点的邻接点被访问。

类似于二叉树的层序遍历

Queue

Queue：基本上，一个队列就是一个先入先出（FIFO）的数据结构

Queue 接口与 List、Set 同一级别，都是继承了 Collection 接口。LinkedList 实现了 Deque 接口。

add：增加一个元索，如果队列已满，则抛出一个 IIIegaISlabEepeplian 异常
remove：移除并返回队列头部的元素如果队列为空，则抛出一个 NoSuchElementException 异常
element：返回队列头部的元素，如果队列为空，则抛出一个 NoSuchElementException 异常
offer：添加一个元素并返回 true，如果队列已满，则返回 false
poll：移除并返问队列头部的元素，如果队列为空，则返回 null
peek：返回队列头部的元素，如果队列为空，则返回 null
put：添加一个元素，如果队列满，则阻塞
take：移除并返回队列头部的元素，如果队列为空，则阻塞

注意：poll 和 peek 方法出错进返回 null。因此，向队列中插入 null 值是不合法的

使用广度优先来计算最小深度的原理是看哪边先遇到叶子结点

	static int BFSMinDepth(TreeNode root){
	// 如果节点是否为空则返回 0
	if (root == null) return 0;
	Queue<TreeNode> queue = new LinkedList<>();
	root.depth=1;
	// 将根节点入队
	queue.offer(root);
	while (!queue.isEmpty()){
	// 取出队列最上面的那个节点，并移除它
	TreeNode node = queue.poll();
	// 如果这个节点是个叶子节点，那么就直接找到最小深度了
	if (node.left== null && node.right==null){
	return node.depth;
	}
	if (node.left!=null){
	node.left.depth=node.depth+1;
	queue.offer(node.left);
	}
	if (node.right!=null){
	node.right.depth=node.depth+1;
	queue.offer(node.right);
	}
	}
	// 一般来说不会走到这里
	return -1;
	}

主方法及控制台说明：

	public static void main(String[] args) {
	TreeNode node5 = new TreeNode(5);
	TreeNode node4 = new TreeNode(4);
	TreeNode node3 = new TreeNode(3, node4, null);
	TreeNode node2 = new TreeNode(2, null, node5);
	TreeNode node1 = new TreeNode(1, node3, null);
	TreeNode root = new TreeNode(0, node1, node2);
	System.out.println(BFSMinDepth(root));
	}
	// 树的样子：
	// 0
	// / \
	// 1 2
	// / \
	// 3 5
	// /
	// 4
	// 控制台输出：3，最小深度是 3 此算法的查找执行顺序是：0->1->2->3->5
	// 不会走到 4 的原因是在 5 已结是叶子节点了

有待更新…

算法

# 最小深度算法

# 深度优先算法（DFS）

# 广度优先搜索（BFS)

算法之合并数组

桃花源记(诡异版)