Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

※ 引述 《oin1104 (是oin的說)》 之銘言：
: 　
: 　
: 　
: 題目 :
: 給你叫做root的樹
: 還有distance
: 問你樹上所有的兩個葉子之間
: 在樹上的距離小於等於distance
: 的組合有多少



剛剛看到一個很屌的
好像是正解

就是先假設
有兩個葉子
一個在左邊
深度是1
一個在右邊
深度是2
這樣只要知道他們的深度
就可以知道他們的距離了

這算什麼演算法阿
不太像lca

然後利用這個去對每個root的葉子
做一次看相加有沒有小於的相乘

在dfs的時候要用vector 的函式 然後姆咪
讓左邊跟右邊的vector 互相看
而他們自己都已經是處理完的了
然後
姆咪

可以過濾掉太大的回傳的值



時間複雜度是n*D^2
不過D很小 所以可以看成n




class Solution {
public:
    int res ;
    int d ;
    vector<int> find(TreeNode* root )
    {
        if(root==NULL)return{};
        if(root->left==NULL && root->right==NULL)return{1};

        vector<int> l = find(root->left);
        vector<int> r = find(root->right);
        vector<int> n ;

        for(int i = 0 ; i < l.size() ; i ++)
        {
            for(int j = 0 ; j < r.size() ; j ++)
            {
                if(l[i]+r[j] <= d)res ++;
            }
        }
        for(int i = 0 ; i < l.size() ; i ++)
        {
            if(l[i]+1 <= d)n.push_back(l[i]+1);
        }
        for(int j = 0 ; j < r.size() ; j ++)
        {
            if(r[j]+1 <= d)n.push_back(r[j]+1);
        }

        return n;
    }

    int countPairs(TreeNode* root, int distance)
    {
        res = 0;
        d = distance;
        find(root);
        return res;
    }
};
```


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.33.183 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721265164.A.3C7.html
推 JIWP: 你模型沒了
推 sustainer123: 最佳解不是LCA喔? 真假
→ oin1104: 我不知道欸
→ sustainer123: 我看著也不像LCA
→ oin1104: 這個應該會比lca好 lca是用hash記祖先 然後每個看吧
→ oin1104: 這個比較像是在每個小的樹上面看d個葉子
→ oin1104: 我看解說是說 這個的時間複雜度比較好 吧
→ SydLrio: 你有什麼用