1530. Number of Good Leaf Nodes Pairs

Link

Solution

   int ret = 0;
    public int countPairs(TreeNode root, int distance) {
        dfs(root, distance);
        return ret;
    }
    
    public Map<Integer, Integer> dfs(TreeNode node, int distance){
        
        Map<Integer, Integer> result = new HashMap<>();
        
        if(node == null) return result;
        
        if(node.left == null && node.right == null){
            result.put(1,1); //遞迴時的處理，可以給予最初始的狀態，之後的狀態會透過初始狀態去推演出來，而不需要設計通則
            return result;
        }
        
        Map<Integer, Integer> left = dfs(node.left, distance);
        Map<Integer, Integer> right = dfs(node.right, distance);
        
        for(int leftDepth : left.keySet()){
            for(int rightDepth : right.keySet()){
                if(leftDepth + rightDepth <= distance){
                    ret += left.get(leftDepth) * right.get(rightDepth);
                }
            }
            if(leftDepth+1 < distance){
                result.put(leftDepth+1, left.get(leftDepth));
            }
        }
        for(int rightDepth : right.keySet()){
            if(rightDepth+1 < distance){
                result.compute(rightDepth+1, (k,v)->{
                    if(v == null){    
                        return right.get(rightDepth);
                    }
                    else{
                        
                        return v + right.get(rightDepth);
                    }
                });
            }
        }
        
        return result;
    }