# 最小深度算法

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

都是要访问完全部节点的,根据访问节点的顺序与方式,可以分为广度优先算法(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,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。

遍历规则:

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

类似于二叉树的层序遍历

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 已结是叶子节点了

有待更新…