[数据结构与算法]力扣1530——好叶子节点对的数量（DFS）

解题思路

最短路径，即通过最近公共祖先，也就是两叶子节点对于当前根来说分属左右两边；
分别用l_leaf和r_leaf存左右两边的叶子节点，通过dfs递归实现，在处理当前根的时候认为左右两边的叶子节点已求得；
两重循环遍历左右叶子节点们，看两两配对能否满足条件；
之后将左右叶子节点分别+1并合并，即是当前根的所有叶子节点；

代码

class Solution {
public:
    int ans = 0;
    vector<int> dfs(TreeNode* root, int distance) {
        if(root == nullptr) return {};
        if(root->left == nullptr && root->right == nullptr) return {1};
        vector<int> l_leaf = dfs(root->left, distance);
        vector<int> r_leaf = dfs(root->right, distance);
        for(auto l : l_leaf) {
            for(auto r : r_leaf) {
                if((l + r) <= distance) ans++;
            }
        }
        for(auto& l : l_leaf) l++;
        for(auto& r : r_leaf) r++;
        l_leaf.insert(l_leaf.end(), r_leaf.begin(), r_leaf.end());
        return l_leaf;
    }
    int countPairs(TreeNode* root, int distance) {
        if(distance == 1) return 0;
        dfs(root, distance);
        return ans;
    }
};