Bölünmüş İkili Ağac LeetCode Həllinin Maksimum Məhsulu

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon ByteDance microsoftBaxılıb 69

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

LinkedInBuferRedditTumblr

Problem bəyanat

Bölünmüş İkili Ağac LeetCode Həllinin Maksimum Məhsulu – Nəzərə alınmaqla root ikili ağacın bir kənarını çıxararaq ikili ağacı iki alt ağaca ayırın ki, alt ağacların cəminin hasili maksimum olsun.

Qayıtmaq iki alt ağacın cəminin maksimum məhsulu. Cavab çox böyük ola bildiyi üçün onu qaytarın modul 109 + 7.

Qeyd mod götürdükdən sonra deyil, qəbul etməzdən əvvəl cavabı artırmaq lazımdır.

Bölünmüş İkili Ağac LeetCode Həllinin Maksimum MəhsuluPin

Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)

Izahat

Problemi oxuyanda bu problem çox çətin görünür. Ağlıma gələn yanaşmalar bunlardır: -

  • Ağacı massiləyə çevirək və sonra cəminin maksimum hasili ilə massivi iki alt çoxluğa bölək. Bu yanaşma işlək görünür, lakin parçalanmış ağacı alacağımıza zəmanət vermir.
  • İndi təsadüfi olaraq müxtəlif həlləri düşünərək, Bəlkə DP, Bəlkə BFS, Bəlkə DFS… Mən bunun pis olduğunu bilmirəm!!!!. Bitirdim, növbəti suala keçirəm.
  • Ancaq gözləyin aşağıda bir ipucu var, gəlin bunu oxuyaq, Əgər alt ağacın cəmini biliriksə, cavab hər bir qovşaqda max( (total_sum – subtree_sum) * subtree_sum) olur.
  • İpucu 4 dəfə oxudum, sonra veriləni çevirdim ağac cəminə çevrilir ağac. Cəmi ağacında hər bir qovşaq sol alt ağacının və sağ alt ağacının cəmini ehtiva edir. Bunu həm kvadratik zamanda, həm də xətti vaxtda edə bilərsiniz, (Kodda xətti zaman həllini tətbiq etdim).
  • İndi nə olacaq, bu cəmi ağacı ilə nə əldə edə bilərəm? Yenidən ipucunu oxuyun, sonra nəhayət ideyaya gəlin. Cəmi ağacınız olduqda, o zaman nəyi gözləyirsiniz, sadəcə olaraq hər bir mümkün kənardan bölün və maksimum nəticə əldə edin.
  • Niyə əvvəllər bunu görmədim!. Bir həqiqət qalib gəlir! (Case Closed azarkeşləri Sarkazm alır).

Bölünmüş İkili Ağac LeetCode Həllinin Maksimum MəhsuluPin

Kodu

Bölünmüş İkili Ağacın Maksimum Məhsulu üçün C++ Kodu

class Solution {
    int tot = 0;
    int mod = 1e9+7;
public:
    // function to convert the tree into sum tree - this works in linear time
    int convert_To_SumTree(TreeNode* root) {
        if(root == NULL)    return 0;
        if(root->left == NULL and root->right == NULL)
            return root->val;
        int leftSum = convert_To_SumTree(root->left);
        int rightSum = convert_To_SumTree(root->right);
        
        root->val += leftSum+rightSum;
        return root->val;
    }
    void splitTree(TreeNode* root, long long& res) {
        if(root == NULL)
            return;
        
        // maximise sum from left
        if(root->left) {
            long long sum1 = root->left->val;
            long long sum2 = tot - sum1;
            long long curr = sum1*sum2;
            if(curr > res)
                res = curr;
        }
        
        // maximise sum from right
        if(root->right) {
            long long sum1 = root->right->val;
            long long sum2 = tot - sum1;
            long long curr = sum1*sum2;
            if(curr > res)
                res = curr;
        }
        
        // call  for left and right
        splitTree(root->left, res);
        splitTree(root->right, res);
    }
    int maxProduct(TreeNode* root) {
        // convert the tree into sum tree
        // so that each node stores the sum of its
        // left and right subtrees
        tot = convert_To_SumTree(root);
        
        if(tot == 0)    return 0;
        
        // now try to split at every location 
        // and get the maximum ans
        long long res = 0;
        splitTree(root, res);
        return res%mod;
    }
};

Bölünmüş İkili Ağacın Maksimum Məhsulu üçün Java Kodu

class Solution {
      int MOD = (int) (1e9) + 7;

    public int maxProduct(TreeNode root) {
        Set<Long> sums = new HashSet<>();
        int total = dfs(root, sums);
        long max = 0;
        for (long sum : sums) {
            max = Math.max(max, sum * (total - sum));
        }
        return (int) (max % MOD);
    }

    public int dfs(TreeNode root, Set<Long> sums) {
        if (root == null)
            return 0;
        root.val += dfs(root.left, sums);
        root.val += dfs(root.right, sums);
        sums.add((long) (root.val));
        return root.val;
    }
}

Bölünmüş İkili Ağacın Maksimum Məhsulu üçün Python Kodu

class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if root == None: return 0
            currSum = dfs(root.left) + dfs(root.right) + root.val
            self.ans = max(self.ans, currSum * (self.totalSum - currSum))
            return currSum

        self.ans, self.totalSum = 0, 0
        self.totalSum = dfs(root)  # Firstly, get total sum of all nodes in the Binary Tree
        dfs(root)  # Then dfs in post order to calculate sum of each subtree and its complement
        return self.ans % (10 ** 9 + 7)

Bölünmüş İkili Ağacın Maksimum Məhsulu üçün Mürəkkəblik Təhlili LeetCode Həllinin

Zamanın mürəkkəbliyi

  • Saat: O(N), Harada N <= 5*10^4 İkili ağacdakı qovşaqların sayıdır.

Kosmik Mürəkkəblik

LinkedInBuferRedditTumblr
Crack Sistemi Dizayn Müsahibələri
Translate »