1530

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
int ans = 0;
public:
    int countPairs(TreeNode* root, int distance) {
        dfs(root, distance);
        return ans;
    }

    vector<int> dfs(TreeNode *node, int distance){
        vector<int> dist(11, 0);
        if(!node) return dist;

        // Leaf node.
        if(!node->left && !node->right){
            dist[1] = 1;
            return dist;
        }

        vector<int> left = dfs(node->left, distance);
        vector<int> right = dfs(node->right, distance);

        // Check for all possible combinations and update the answer.
        for(int i=0; i<=10;  i++)
            for(int j=0; j<=10; j++)
                if(i+j <= distance)
                    ans += left[i]*right[j];

        // Update distance array.
        for(int i=0; i<10; i++)
            dist[i+1] = left[i]+right[i];

        return dist;
    }
};