<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 {
// public:
//     int cnt=0;
//     vector<int> add_v( vector<int> v, vector<int> z ){
//         vector<int> new_v;
//         int i=0,j=0;
//         while(i<v.size() && j<z.size()){
//             if(v[i]<z[j]){
//                 new_v.push_back(v[i]);
//                 i++;
//             }else{
//                 new_v.push_back(z[j]);
//                 j++;
//             }
//         }
//         while(i<v.size()){
//             new_v.push_back(v[i]);
//             i++;
//         }
//         while(j<z.size()){
//             new_v.push_back(z[j]);
//             j++;
//         }
//         return new_v;
//     }
//     vector<int> dfs(TreeNode* root, int d, vector<int> v) {
//         if(root->left==NULL && root->right==NULL){
//             while(v.size()>0){
//                 if(v.back()<=d){
//                     cnt++;
//                 }
//                 v.pop_back();
//             }
//             v = {0};
//             // return z;
//         }
//         if(root->left){
//             vector<int> k;
//             for(int i=0;i<v.size();i++){
//                 k.push_back(v[i]+1);
//             }
//             vector<int> z = dfs(root->left, d, k);
//             vector<int> new_v = add_v(v,z);
//             // cout<<new_v.back()<<endl;
//             while(new_v.back()>=d){
//                 new_v.pop_back();
//             }
//             v = new_v;
//         }
//         if(root->right){
//             vector<int> k;
//             for(int i=0;i<v.size();i++){
//                 k.push_back(v[i]+1);
//             }
//             vector<int> z = dfs(root->right, d, k);
//             vector<int> new_v = add_v(v,z);
//             v = new_v;
//         }
//         // increament all to 1
//         for(int i=0;i<v.size();i++){
//             v[i] = v[i]+1;
//         }
//         return v;
        
//     }

//     int countPairs(TreeNode* root, int distance) {
//         vector<int> v;
//         vector<int> vv = dfs(root, distance, v);
//         return cnt;
//     }
// };

class Solution {
public:
    int cnt=0;
    vector<int> add_v( vector<int> v, vector<int> z, int d ){
        vector<int> new_v;
        int i=0,j=0;
        while(i<v.size() && j<z.size()){
            if(v[i]<z[j]+1){
                new_v.push_back(v[i]);
                i++;
            }else{
                new_v.push_back(z[j]+1);
                j++;
            }
        }
        while(i<v.size()){
            new_v.push_back(v[i]);
            i++;
        }
        while(j<z.size()){
            new_v.push_back(z[j]+1);
            j++;
        }
        while(!new_v.empty() && new_v.back()>d){
            new_v.pop_back();
        }
        return new_v;
    }
    vector<int> add_( vector<int> v, vector<int> z, int d ){
        vector<int> new_v;
        int i=0,j=0;
        while(i<v.size() && j<z.size()){
            if(v[i]<z[j]){
                new_v.push_back(v[i]+1);
                i++;
            }else{
                new_v.push_back(z[j]+1);
                j++;
            }
        }
        while(i<v.size()){
            new_v.push_back(v[i]+1);
            i++;
        }
        while(j<z.size()){
            new_v.push_back(z[j]+1);
            j++;
        }
        while(!new_v.empty() && new_v.back()>d){
            new_v.pop_back();
        }
        return new_v;
    }
    vector<int> dfs(TreeNode* root, int d, vector<int> v) {
        for(int i=0;i<v.size();i++){
            v[i] = v[i]+1;
        }
        if(root->left==NULL && root->right==NULL){
            while(v.size()>0){
                if(v.back()<=d){
                    cnt +=1;
                    // cnt += v.size();
                    // break;
                }
                v.pop_back();
            }
            vector<int> z = {0};
            return z;
        }
        vector<int> z1,z2;
        if(root->left){
            z1 = dfs(root->left, d, v);
            vector<int> new_v = add_v(v,z1,d);
            v = new_v;
        }
        if(root->right){
            z2 = dfs(root->right, d, v);
            vector<int> new_v = add_v(v,z2,d);
            v = new_v;
        }
        return add_(z1,z2,d);

        // for(auto i:v){
        //     cout<<i<<" ";
        // }
        // cout<<endl;
        // return v;
    }

    int countPairs(TreeNode* root, int distance) {
        vector<int> v;
        vector<int> vv = dfs(root, distance, v);
        return cnt;
    }
};
73568