leetcode 1530. Number of Good Leaf Nodes Pairs LCA 最近公共祖先

题目

https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/
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:

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:

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].
Example 4:

Input: root = [100], distance = 1
Output: 0
Example 5:

Input: root = [1,1,1], distance = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 2^10].
Each node’s value is between [1, 100].
1 <= distance <= 10

思路

对于dfs分别计算两个子树中的叶子对数,然后再求叶子分别处于两个子树中的对数。
对于每颗子树返回其中的对数,和每层叶子节点的数量,即只记录叶子节点所在层数,不记录dfs路径长度,而后两个叶子节点的距离即为深度和
这样可以避免重复,左右子树中的叶子节点都以当前节点为 LCA ,最近公共祖先

源码

/**
 * 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) {}
 * };
 */
struct RES{
    int cnt = 0;
    vector<pair<int,int>> dis;
};
class Solution {
public:
    int dd;
    int countPairs(TreeNode* root, int distance) {
        dd = distance;
       RES res =  dfs(root);
        return res.cnt;
    }
    RES dfs(TreeNode* root){
        RES res;
        if(root == NULL)return res;
        if(root->left==NULL&&root->right==NULL)
            res.dis.push_back(make_pair(0,1));
        RES l = dfs(root->left);
        RES r = dfs(root->right);
        res.cnt = l.cnt+r.cnt;
        for(int i = 0;i < l.dis.size();++i){
            for(int j = 0;j < r.dis.size();++j){
                pair<int,int> ll = l.dis[i];
                pair<int,int> rr = r.dis[j];
               // cout << ll.first<<" "<<rr.first<<" d: "<<ll.second<<" "<<rr.second<<endl;
                if(ll.first+rr.first+2<=dd){
                    res.cnt+=ll.second*rr.second;
                }
            }
        }
      //  cout << l.cnt<<endl;
        //cout << r.cnt<<endl<<endl;
        map<int,int> m;
        for(auto p:l.dis){
            m[p.first]+=p.second;
        }
        for(auto p:r.dis){
            m[p.first]+=p.second;
        }
        for(auto p:m){
            res.dis.push_back(make_pair(p.first+1,p.second));
        }
        return res;
    }
};

discuss 里看见一份代码同样的逻辑后续遍历,人家代码写的就贼优雅

/*
    https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/submissions/

    Idea is to find out the distance of leaf nodes in left and right subtrees
    for each of the parent nodes. For a node 'i', if we know the distance of leaf nodes
    in its left and right from it, then we can just check if the sum of distance of the leaf nodes
    in left and right <= dist limit, that makes it a good pair.

*/

/**
 * 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:
    // TC: O(n * d * d), d: max distance limit, n: num of nodes
    vector<int> postOrder(TreeNode *root, int &distance,
                          int &good_leaves) {
        // dist(i): no. of leaf nodes with dist 'i' from current node
        vector<int> dist(distance + 1, 0);
        if(!root)
            return dist;

        // when current is a leaf node, its distance with its parent will be 1
        if(!root->left && !root->right) {
            dist[1] = 1;
            return dist;
        }

        // find the distance of leaf and right subtree leaf nodes
        auto left_dist = postOrder(root->left, distance, good_leaves);
        auto right_dist = postOrder(root->right, distance, good_leaves);

        // now check the distances between leaf nodes of leaf and right 
        // subtrees which are under limit
        for(int i = 0; i < left_dist.size(); i++)
            for(int j = 0; j < right_dist.size(); j++)
                if(i + j <= distance) {
                    good_leaves += (left_dist[i] * right_dist[j]);
                }
        // Update the distance for parent and include the current node
        for(int i = 1; i <= distance; i++) {
            // (i-1) distance becomes distance 'i' 
            dist[i] = left_dist[i-1] + right_dist[i-1];
        }

        return dist;
    }


    int countPairs(TreeNode* root, int distance) {
        int good_leaves = 0, curr_dist = -1;
        postOrder(root, distance, good_leaves);
        return good_leaves;
    }
};

发表评论

邮箱地址不会被公开。 必填项已用*标注