一、深度优先搜索
深度优先搜索属于图算法的一种,是一个针对图和树的遍历算法,英文缩写为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;
}
}