DFS深度优先算法总结

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

class Solution {
    //这题首先想到通过Math.max做比较实现，也就是提前顶一个一个最大值max，通过max与root.val+root.left.val+root.right.val进行比较
    //更大的设置为max
    int sum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return sum;
    }
    public int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
        //通过递归计算左右子树
        int sumLeft = Math.max(dfs(root.left),0);
        int sumRight = Math.max(dfs(root.right),0);
        //节点值相加
        int sumRoot = root.val+sumLeft+sumRight;
        //将节点最大值与定义的max做比较
        sum = Math.max(sumRoot,sum);
        return root.val+Math.max(sumLeft,sumRight);
    }
}

你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。

class Solution {
    public int[] pondSizes(int[][] land) {
    //这里不要用set，set虽然会有序，但是不能重复，
    //所以会将许多数据过滤，用List，最后通过sort方法进行排序
        List list = new ArrayList();
        if(land.length==0)  return new int [0];
        for(int i = 0;i<land.length;i++){
            for(int j=0;j<land[0].length;j++){
                if(land[i][j]==0){
                    list.add(dfs(land,i,j));
                }
            }
        }
        list.sort((o1,o2)-> o1-o2);
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
    //深度优先算法，类似岛屿的问题，岛屿的问题不计算对角线，这里需要计算对角线
    public int dfs(int[][] land,int i,int j){
        //设定返回条件
        if(i<0 || j<0 || i >= land.length || j >= land[0].length || land[i][j] != 0){
            return 0;
        }
        //设置标志位，标记该点已被搜索
        land[i][j] = -1;
        //初始化池塘大小
        int value = 1;
        //计算池塘大小，从垂直、水平、对角线计算
        value += dfs(land,i-1,j-1);
        value += dfs(land,i-1,j+1);
        value += dfs(land,i-1,j);
        value += dfs(land,i,j-1);
        value += dfs(land,i,j+1);
        value += dfs(land,i+1,j-1);
        value += dfs(land,i+1,j+1);
        value += dfs(land,i+1,j);
        return value;
    }
}

根据一棵树的前序遍历与中序遍历构造二叉树。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null && inorder == null) return null;
        return dfs(preorder,inorder,0,preorder.length,0,inorder.length);
    }

    public TreeNode dfs(int[] pre,int[] mid,int preLeft,int preRight,int midLeft,int midRight){
        if(preLeft == preRight){
            return null;
        }

        //设置根节点
        TreeNode res = new TreeNode(pre[preLeft]);


        int index = 0;

        for(int i=midLeft;i<midRight;i++){
            if(pre[preLeft] == mid[i]){
                index = i;
                break;
            }
        }
        res.left = dfs(pre,mid,preLeft+1,preLeft+index-midLeft+1,midLeft,index);
        res.right = dfs(pre,mid,preLeft+index-midLeft+1,preRight,index+1,midRight);

        return res;


    }
}