<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>

class Solution {
    void make_parent(TreeNode *node, map<TreeNode*, TreeNode*> &parent){
        if(node->left){
            parent[node->left] = node;
            make_parent(node->left,parent);
        }        
        if(node->right){
            parent[node->right] = node;
            make_parent(node->right,parent);
        }        
    }

    void dfs(TreeNode* node, int distance, map<TreeNode*,bool> &local_visited, map<TreeNode*,bool> &global_visited, map<TreeNode*,TreeNode*> &parent, int &good_pairs ){
        if(distance < 0) return;
        

        if(!node->left && !node->right && !global_visited[node]){
            good_pairs++;
        }

        local_visited[node] = true;

        TreeNode * parent_node = parent[node];

        if(node->left && !local_visited[node->left]) dfs(node->left, distance-1, local_visited,global_visited, parent, good_pairs);
        if(node->right && !local_visited[node->right]) dfs(node->right, distance-1, local_visited,global_visited, parent, good_pairs);
        if(parent_node && !local_visited[parent_node]) dfs(parent_node, distance-1, local_visited,global_visited, parent, good_pairs);
    }

    void traverse(TreeNode* node, int distance, map<TreeNode*,bool> &global_visited,map<TreeNode*,TreeNode*> &parent, int &good_pairs ){
        if(!node) return;
        if(!node->left && !node->right){
            map<TreeNode*,bool> local_visited; 
            global_visited[node] = true;
            dfs(node, distance, local_visited, global_visited, parent, good_pairs);
        }
        traverse(node->left, distance, global_visited, parent, good_pairs);
        traverse(node->right, distance, global_visited, parent, good_pairs);
    }

public:
    int countPairs(TreeNode* root, int distance) {
        int good_pairs=0;
        map<TreeNode*, TreeNode*> parent;
        map<TreeNode*,bool> visited;
        make_parent(root,parent);
        traverse(root, distance, visited, parent, good_pairs);
        return good_pairs; 
    }
};

137918