1530. Number of Good Leaf Nodes Pairs

Myth丶恋晨 2024-04-07 13:55 70阅读 0赞

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

Return *the number of good leaf node pairs* in the tree.

**Example 1:**

![593b61bbba21f9729b2c0d73be2d81d8.jpeg][]

Input: root = [1,2,3,null,4], distance = 3
    Output: 1
    Explanation: 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.

**Example 2:**

![8866d0fd1bab746d477eea4624c0a8a0.jpeg][]

Input: root = [1,2,3,4,5,6,7], distance = 3
    Output: 2
    Explanation: 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.

**Example 3:**

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

题目：给定一个二叉树，找出good pair的数量，good pair是距离路径长度小于给定值distance的叶子对。

思路：叶子不可能直接与叶子相通，必然是通过一个共同的父结点或祖辈节点，需要记录以每个节点作为根节点的子树下有几个叶子节点，且叶子节点离当前子根节点的距离。可递归为计算其左节点下的叶子节点和其右节点下的叶子节点，计算其所有左叶子节点和所有右叶子节点的距离（为其左叶子节点距离当前节点的距离+右叶子节点距离当前节点的距离），如距离小于给定distance，则更新结果。最后将其所有左叶子节点和所有右叶子节点整合，为当前节点的所有子叶子节点。用hashmap记录。

注：hasmap的key记录当前子节点所有叶子节点的距离，value记录某一距离的叶子节点的个数

代码：

/**
     * 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:
        unordered_map<int, int> helper(TreeNode* node, int dis, int& res){
            if(!node) return {};
            unordered_map<int, int> left = helper(node->left, dis, res);
            unordered_map<int, int> right = helper(node->right, dis, res);
            unordered_map<int, int> out;
            if(left.empty() && right.empty()){
                out[0] = 1;
            } else {
                for(auto l : left){
                    out[l.first + 1] += l.second;
                    for(auto r : right){
                        if (l.first + r.first + 2 <= dis){
                            res += l.second * r.second;
                        }
                    }
                }
                for(auto r : right){
                    out[r.first+1] += r.second;
                }
            }
            return out;
        }
        int countPairs(TreeNode* root, int distance) {
            int res = 0;
            helper(root, distance, res);
            return res;
        }
    };

[593b61bbba21f9729b2c0d73be2d81d8.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/46e37b300e3840f2a5a8fa492583d77d.jpeg
[8866d0fd1bab746d477eea4624c0a8a0.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/58f2d24854bb4a61b19d47a97dc1a1bd.jpeg