深度优先搜索和广度优先搜索

一、深度优先搜索

深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，方便的解决很多相关的图论问题。
其过程为遍历分支路径深入到不能再深入为止，且每个节点只能访问一次。
一般用堆数据结构来辅助实现DFS算法。如最大路径问题等等。
缺点难以寻找最优解，仅仅只能寻找有解。
class Solution {
    int res = 0;
    int maxdepth = 0;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root,0);
        return res;
    }
    public void dfs(TreeNode node,int depth){
        if(node==null) return ;
        if(depth>maxdepth){
            res = node.val;
            maxdepth = depth;
        }
        dfs(node.left,depth+1);
        dfs(node.right,depth+1);
    }
}

二、广度优先搜索

广度优先搜索（也称宽度优先搜索，缩写BFS）是连通图的一种遍历算法。
属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。
从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。
一般用队列数据结构来辅助实现BFS算法。
适用于节点的子节点数不多，并且树的层次不会太深的情况
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            if(root.right!=null) queue.offer(root.right);
            if(root.left!=null) queue.offer(root.left);
        }
        return root.val;
    }
}