<p>You are given the <code>root</code> of a binary tree and an integer <code>distance</code>. A pair of two different <strong>leaf</strong> nodes of a binary tree is said to be good if the length of <strong>the shortest path</strong> between them is less than or equal to <code>distance</code>.</p>

<p>Return <em>the number of good leaf node pairs</em> in the tree.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/07/09/e1.jpg" style="width: 250px; height: 250px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,null,4], distance = 3
<strong>Output:</strong> 1
<strong>Explanation:</strong> The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/07/09/e2.jpg" style="width: 250px; height: 182px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,4,5,6,7], distance = 3
<strong>Output:</strong> 2
<strong>Explanation:</strong> The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
<strong>Output:</strong> 1
<strong>Explanation:</strong> The only good pair is [2,5].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the <code>tree</code> is in the range <code>[1, 2<sup>10</sup>].</code></li>
	<li><code>1 &lt;= Node.val &lt;= 100</code></li>
	<li><code>1 &lt;= distance &lt;= 10</code></li>
</ul>

#include <unordered_map>

/**
 * 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 {
public:
    /*
        [INTUITION / SKETCH]
        -Note that we can recursively deconstruct this problem 
        into subproblems
        -The number of good pairs for a 'root' is the sum of:
            (1) The number of good pairs from 'root->left',
            assuming it exists
            (2) The number of good pairs from 'root->right',
            assuming it exists
            (3) Pairs with one leaf node from 'root->left'
            and one leaf node from 'root->right', assuming they
            both exist
        -To determine (3), we need to know how many nodes occur
        at a given depth from both children
            -Let 'd' be the maximal distance
            -Then, the number of pairs under (3) is:
                - (# "left leaves" (LL) of distance 2) * (# "right leaves" (RL) of distance <= (d - 2))
                - (LL dist 3) * (RL dist <= (d - 3))
                (...)
                - (LL dist (d - 2)) * (RL dist <= 2)
            -Thus, our return value from our recursive calls should be this^^
            "distance map"
        -Because we need the results from our children first, to compute 
        our own result, this also implies a postorder (recursive) traversal

        -Note: Because we have a return value from our recursive calls & it's
        not a shared variable, we need to be careful about space complexity here

        [PSEUDOCODE]
        -def dfs(root, maxDistance, goodPairs):
            # Note: Store only distances <= 'maxDistance' (which whill be <= 10)
            -leftMap = {} # Distances from 'root' to descendant leaf nodes of 'root.left'
            -rightMap = {} # Distances from 'root' to descendant leaf nodes of 'root.right'

            -if root.left:
                -leftChildMaps = dfs(root.left, currDepth + 1, goodPairs)
                -Copy over 'leftChildMaps' into leftMap, incrementing the 'distance' keys
            
            -if root.right:
                <ditto> as 'root.left'

            -increment 'goodPairs' by parsing 'leftMap' and 'rightMap' (see above)
                -Note: Write a helper function for this

            -return [leftMap, rightMap]
    */

    void enumDists(vector<int>& dist)
    {
        for (int i = 0; i < dist.size(); ++i)
        {
            cout << i << ": " << dist[i];
            if (i < dist.size() - 1) { cout << ", "; }
        }
        cout << "\n";
    }

    void addNewPairs(
        int& goodPairs, 
        vector<int>& leftDists, 
        vector<int>& rightDists, 
        int maxDist
    )
    {
        int rightLeaves = 0;
        for (int d = 0; d <= maxDist; ++d) { rightLeaves += rightDists[d]; }

        for (int leftDist = 0; leftDist <= maxDist; ++leftDist)
        {
            goodPairs += (leftDists[leftDist]) * rightLeaves;

            int maxRightDist = maxDist - leftDist;
            rightLeaves -= rightDists[maxRightDist];
        }
    }

    vector<vector<int>> dfs(
        int& goodPairs,
        TreeNode* root,
        int maxDist,
        int side // 0 ->left child, 1 ->right child
    )
    {
        vector<int> leftDists(maxDist + 1, 0);
        vector<int> rightDists(maxDist + 1, 0);

        if (!root) { return { leftDists, rightDists }; }
        if (!root->left & !root->right)
        {
            if (!side) { ++leftDists[0]; }
            else { ++rightDists[0]; }
            return { leftDists, rightDists };
        }
  
        if (root->left)
        {
            vector<vector<int>> leftChildDists = dfs(goodPairs, root->left, maxDist, 0);

            for (int i = 0; i < maxDist; ++i)
            {
                leftDists[i + 1] += leftChildDists[0][i];
                leftDists[i + 1] += leftChildDists[1][i];
            }
        }

        if (root->right)
        {
            vector<vector<int>> rightChildDists = dfs(goodPairs, root->right, maxDist, 1);

            for (int i = 0; i < maxDist; ++i)
            {
                rightDists[i + 1] += rightChildDists[0][i];
                rightDists[i + 1] += rightChildDists[1][i];
            }
        }

        addNewPairs(goodPairs, leftDists, rightDists, maxDist);
        return { leftDists, rightDists };
    }

    int countPairs(TreeNode* root, int distance) 
    {
        int goodPairs = 0;
        dfs(goodPairs, root, distance, -1);
        return goodPairs;
    }
};
60406