当前位置：网站首页>[brother hero July training] day 15: depth first search

class Solution {
    
    public boolean isleaf(TreeNode root) {
    
        return root.left==null&&root.right==null;
    }

    public boolean evaluateTree(TreeNode root) {
    
        
        if(root!=null){
    
            if(!isleaf(root)){
    
                boolean L = evaluateTree(root.left);
                boolean R = evaluateTree(root.right);
                if(root.val==2){
    
                    return L|R;
                } else {
    
                    return L&R;
                }

            }
            return root.val==0?false:true;
        }
        return false;

    }
}

Two 、 Flip the equivalent binary tree

951. Flip the equivalent binary tree

leetcode951 java

class Solution {
    
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
    
        if(root1==null&&root2==null){
    
            return true;
        }
        if(root1!=null&&root2!=null){
    
            if(root1.val!=root2.val){
    
                return false;
            }
            if(flipEquiv(root1.left,root2.left)&&flipEquiv(root1.right,root2.right)){
    
                return true;
            };
            if(flipEquiv(root1.left,root2.right)&&flipEquiv(root1.right,root2.left)){
    
                return true;
            };
            return false;
        }
        
        return false;

    }
}

3、 ... and 、 Find all the farm groups

1992. Find all the farm groups

leetcode1992 java

class Solution {
    
    int[][] land;
    int m,n;
    int x,y;
    int[][] dirs = {
    {
    1,0},{
    0,1}};
    public int[][] findFarmland(int[][] land) {
    
        this.land=land;
        List<int[]> res = new ArrayList<>();
        m = land.length;
        n = land[0].length;
        
        for(int i = 0;i<m;i++){
    
            for(int j = 0;j<n;j++){
    
                if(land[i][j]==1){
    
                    System.out.printf("%d %d\n",i,j);
                    int[] ans =dfs(i,j);
                    res.add(new int[]{
    i,j,ans[0],ans[1]});
                }
            }
        }
        return res.toArray(new int[0][]);
    }

    public int[] dfs(int i,int j){
    
        int[] ans = new int[]{
    i,j};
        
        for(int[] dir:dirs){
    
            int ni=i+dir[0];
            int nj=j+dir[1];
            if(ni>=m||nj>=n||land[ni][nj]==0){
    
                continue;
            }
            land[ni][nj]=0;
            int[] dfs = dfs(ni,nj);
            ans[0]=Math.max(dfs[0],ans[0]);
            ans[1]=Math.max(dfs[1],ans[1]);
        }
        return ans;
        
        
    }
        
}

Four 、 Look for duplicate subtrees

652. Look for duplicate subtrees

leetcode652 java

class Solution {
    
        List<TreeNode> ans;
        Map<String,Integer> count;
    
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    
        ans = new ArrayList<>();
        count = new HashMap<>();
        collect(root);
        return ans;
    }
    public String collect(TreeNode root){
    
        if(root==null) return "#";
        String series = root.val+","+collect(root.left)+","+collect(root.right);
        count.put(series, count.getOrDefault(series,0)+1);
        if(count.get(series)==2){
    
            ans.add(root);
        }
        return series;
    }
}