力扣199场比赛 5474. 好叶子节点对的数量

力扣199场比赛 5474. 好叶子节点对的数量

给你二叉树的根节点 root 和一个整数 distance 。

如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。

返回树中 好叶子节点对的数量 。

示例 1：

输入：root = [1,2,3,null,4], distance = 3
输出：1
解释：树的叶节点是 3 和 4 ，它们之间的最短路径的长度是 3 。这是唯一的好叶子节点对。
示例 2：

输入：root = [1,2,3,4,5,6,7], distance = 3
输出：2
解释：好叶子节点对为 [4,5] 和 [6,7] ，最短路径长度都是 2 。但是叶子节点对 [4,6] 不满足要求，因为它们之间的最短路径长度为 4 。
示例 3：

输入：root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
输出：1
解释：唯一的好叶子节点对是 [2,5] 。
示例 4：

输入：root = [100], distance = 1
输出：0
示例 5：

输入：root = [1,1,1], distance = 2
输出：1

提示：

tree 的节点数在 [1, 2^10] 范围内。
每个节点的值都在 [1, 100] 之间。
1 <= distance <= 10

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题主要把握两点：

1. 判断当前节点为叶子节点
2. 计算任意两个叶子节点之间的路径距离，并计算符合要求路径的对数
   判断是否是叶子节点很简单，难点是如何求叶子节点之间的距离？
   对于二叉树，我们可以使用队列进行广度优先遍历，同时每个节点都有对应的唯一的路径，仿照哈夫曼编码，对于当前节点到左结点路径使用0记录，到右结点路径使用1记录，这样可以做到每条路径唯一，如果两个节点（N层）共父亲节点，其对应的路径前缀一定有N-1个相等，如果两个节点间的路径长度，可以转化成两个节点分别到第一个公共祖父节点的路径之和，也就是说可以比较路径编码来判断其第一个公共祖父节点位置。即最后一个编码相同的节点即其第一个公共祖父节点。

如上图所示：
叶子节点4的路径”00“，节点5的路径为”01“，节点6的路径为”10“
，节点7的路径为”11“，那么叶子节点4和5之间的距离可以这么计算：4的路径长度+5的路径长度-2*(4和5节点路径的前缀相同的长度) =》2 + 2 - 2*(1) = 2;括号中的1是00和01的前缀有相同的0，程度为1
叶子节点4和6之间的距离：2+2-2*(0)=4，00和10没有相同的前缀。
同理可以计算节点5和6的距离是4，节点6和7之间的距离是2。
最后统计满足条件的对数即可。

/*** 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) {}* };*/
typedef TreeNode T;
class Solution {
public:int countPairs(TreeNode* root, int distance) {vector<T *> trees;vector<string> sPath;trees.push_back(root);sPath.push_back("");for(int i = 0;i < int(trees.size());i++){T* node = trees[i];string path = sPath[i];if(node->left!=nullptr){trees.push_back(node->left);sPath.push_back(path + "0");}if(node->right!=nullptr){trees.push_back(node->right);sPath.push_back(path + "1");}}int ans = 0;for(int i = 0; i < int(trees.size()); i++){for(int j = i+1; j < int(trees.size()); j++){if(trees[i]->left!=nullptr || trees[i]->right!=nullptr|| trees[j]->left!=nullptr || trees[j]->right!=nullptr)continue;int d = sPath[i].size() + sPath[j].size();for(int k = 0; k < sPath[i].size() && k < sPath[j].size(); k++){if(sPath[i][k]==sPath[j][k]) d -= 2;else break;}if(d <= distance)ans++;}}return ans;}
};