DFS(广度优先搜索)算法通用总结

DFS(广度优先搜索)主要区别于BFS(宽度优先搜索)存在。这里总结一下应用的一些经典题，总结一下模板。广度优先搜索是自顶向下的搜索算法，到达底部的条件在二叉树的情况下就是到达叶子节点。

针对二叉树解题基本模板

这套模板主要针对二叉树，其他的多重路径的条件下还是需要用backtracking，实际上DFS像是二维的backtracking和分治法的结合。

private int sum=0;
    public int sumNumbers(TreeNode root) {
        if (root==null) {
            return 0;
        }
        dfs(root,0);
        return sum;
    }
    public void dfs(TreeNode root,int temp){
				//计算当前节点的值
        int next=temp*10+root.val;
        //只需要判断叶子节点即可
        if (root.left==null && root.right==null) {
            //到达叶子节点
            sum+=next;
        }
        //非叶子节点并且左子树不为空往下继续
        if (root.left!=null) {
            dfs(root.left,next);
        }
        //非叶子节点并且右子树不为空往下继续
        if (root.right!=null) {
            dfs(root.right,next);
        }
    }

P988

这道题通过DFS找出最小的字符串，基本就按照模板去套。

package DepthFirstSearch.P988;

import CommonUtils.TreeNodeUtils;
import P104.TreeNode;

/**
 * @autor yeqiaozhu.
 * @date 2019-11-28
 */
public class UsingStringBuilder {
    public String min=null;
    public String smallestFromLeaf(TreeNode root) {
        if (root==null) {
            return "";
        }
        dfs(root,"");

        return min;
    }

    public void dfs(TreeNode root,String temp){
        String next=(char)(root.val+'a')+temp;
        if (root.left==null && root.right==null) {
            //进行比较并判断大小
            if (min==null) {
                min=next;
            }else {
                min=next.compareTo(min)<0?next:min;
            }
        }
        if (root.left!=null) {
            dfs(root.left,next);
        }
        if (root.right!=null) {
            dfs(root.right,next);
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode= TreeNodeUtils.stringToTreeNode("[0,1,2,3,4,3,4]");
        System.out.println(new Solution().smallestFromLeaf(treeNode));

        TreeNode treeNode1= TreeNodeUtils.stringToTreeNode("[25,1,3,1,3,0,2]");
        System.out.println(new Solution().smallestFromLeaf(treeNode1));

        TreeNode treeNode2= TreeNodeUtils.stringToTreeNode("[25,1,null,0,0,1,null,null,null,0]");
        System.out.println(new UsingStringBuilder().smallestFromLeaf(treeNode2));
    }
}