डावीकडील पाने लेटकोड सोल्यूशन्सची बेरीज  


अडचण पातळी सोपे
वारंवार विचारले अडोब
अल्गोरिदम कोडिंग मुलाखत मुलाखतीची तयारी लेटकोड LeetCodeSolutions झाड ट्री ट्रॅव्हर्सल

या समस्येमध्ये, आम्हाला बायनरीमध्ये सर्व डाव्या पानांची बेरीज शोधणे आवश्यक आहे झाड. एक पाने ज्याला म्हणतात “डावा पत्ता”जर ते झाडातील कोणत्याही नोडचे डावे मूल असेल.

डावीकडील पाने लेटकोड सोल्यूशन्सची बेरीज

उदाहरण    

     2
        
  /     \

4          7

        /      \

      9          4
Sum is 13
2

  \
 
    3
Sum is 0

दृष्टीकोन  

बायनरी ट्रीला ओलांडण्यासाठी आम्ही रिकर्सन वापरू शकतो. जर कोणत्याही नोडला डावे मूल असेल आणि ते देखील एक पाने असेल तर आम्ही आपल्या बेरीजमध्ये डाव्या मुलाचे मूल्य जोडू शकतो. परंतु हा दृष्टीकोन रिकर्सिव स्टॅक स्पेस वापरतो.

आम्ही मेमरीची जागा वाचवू शकणारी इतर कोणत्याही ट्रॅव्हर्सल वापरु शकतो?

मॉरिस इनऑर्डर ट्रॅव्हर्सल प्रत्येक नोडला पुन्हा पुन्हा भेट देण्यासाठी लागू केले जाऊ शकते. यात डाव्या पानांचे मूल आहे की नाही ते तपासा आणि त्यानुसार त्याचे मूल्य जोडा. हा इष्टतम दृष्टीकोन आहे. लक्षात घ्या की जर समस्या आम्हाला झाडाची रचना बदलण्याची परवानगी देत ​​असेल तरच आम्ही "मॉरिस इनऑर्डर ट्रव्हर्सल" लागू करू शकतो.

अल्गोरिदम (रिकर्सिव)  

  1. एक फंक्शन तयार करा बेरीज () जी कोणत्याही पासच्या डाव्या पानांची बेरीज मिळवते मूळ
  2. जर झाडाचे मूळ असेल निरर्थक
    • शून्य परत
  3. जर सध्याच्या मुळात डावे मूल असेल आणि ते a पाने
    • त्याचे मूल्य + बेरीज द्या (रूट-> डावे) + बेरीज + लेफ्टलिव्ह्स (रूट-> उजवीकडे)
  4. रिटर्न योगऑफलिफ्टलाव्ह (रूट-> डावे) + बेरीज (डावे) रूट (रूट-> उजवीकडे)

अल्गोरिदम (मॉरिस इनऑर्डर)  

  1. मॉरिस इनऑर्डर ट्रॅव्हर्सलचा वापर करून बायनरी ओलांडून जा:
    • कोणत्याही नोडच्या डावीकडील उपसृष्टीची स्वतःच्या अंतर्गत पूर्वपरंपराला थ्रेड करा.
    • जर एखादा धागा आधीच अस्तित्त्वात असेल तर झाडाची मूळ रचना टिकवून ठेवू नका.
  2. कोणत्याही नोडच्या डाव्या मुलास पान असल्यास, त्यास परिणामी जोडा.
  3. निकाल प्रिंट करा.
हे सुद्धा पहा
एक टिक टॅक टू गेम लीटकोड सोल्यूशनवर विजेता शोधा

अंमलबजावणी  

सी ++ प्रोग्राम ऑफ बेरीज ऑफ लेफ्टकोड सोल्यूशन्स

रिकर्सिव्ह अ‍ॅप्रोच

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

int sumOfLeftLeaves(treeNode* root)
{
    if(root)
    {
        if(root->left && !root->left->left && !root->left->right)
            return root->left->value + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
        return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
    return 0;
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(4);
    root->right = new treeNode(7);
    root->right->left = new treeNode(9);
    root->right->right =  new treeNode(4);

    cout << "Sum is " << sumOfLeftLeaves(root) << "\n";


    return 0;
}

इष्टतम पद्धत

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

int sumOfLeftLeaves(treeNode* root)
{
    int sum = 0;
    while(root != NULL)
    {
        if(root->left == NULL)
        {
            if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
                sum += root->left->value;
            root = root->right;
        }
        else
        {
            treeNode* temp = root->left;
            while(temp->right != NULL && temp->right != root)
                temp = temp->right;

            if(temp->right == NULL)
            {
                temp->right = root;
                root = root->left;
            }
            else
            {
                temp->right = NULL;
                if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
                    sum += root->left->value;
                root = root->right;
            }
        }
    }
    return sum;
}



int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(4);
    root->right = new treeNode(7);
    root->right->left = new treeNode(9);
    root->right->right =  new treeNode(4);

    cout << "Sum is " << sumOfLeftLeaves(root) << "\n";


    return 0;
}
Sum is 13

डावा पाने लीकोड सोल्यूशन्सच्या योगाचा जावा प्रोग्राम

रिकर्सिव्ह अ‍ॅप्रोच

class treeNode
{
    int value;
    treeNode left, right;
    public treeNode(int x)
    {
        value= x;
        left = right = null;
    }
}

class sum_of_left_leaves
{
    public static int sumOfLeftLeaves(treeNode root)
    {
        if(root == null)
            return 0;
        if(root.left != null && root.left.left == null && root.left.right == null)
            return root.left.value + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(4);
        root.right = new treeNode(7);
        root.right.left = new treeNode(9);
        root.right.right =  new treeNode(4);

        System.out.println("Sum is " + sumOfLeftLeaves(root));
    }
}

इष्टतम पद्धत

int sum = 0;
        while(root != null)
        {
            if(root.left == null)
            {
                if(root.left != null && root.left.left == null && root.left.right == null)
                    sum += root.left.value;
                root = root.right;
            }
            else
            {
                treeNode temp = root.left;
                while(temp.right != null && temp.right != root)
                    temp = temp.right;

                if(temp.right == null)
                {
                    temp.right = root;
                    root = root.left;
                }
                else
                {
                    temp.right = null;
                    if(root.left != null && root.left.left == null && root.left.right == null)
                        sum += root.left.value;
                    root = root.right;
                }
            }
        }
        return sum;
Sum is 13

डाव्या पानांच्या लेटकोड सोल्यूशन्सच्या बेरीजचे गुंतागुंत विश्लेषण  

वेळ कॉम्प्लेक्सिटी

ओ (एन), जसे आपण वारंवार आणि पुनरावृत्ती करण्याच्या दृष्टिकोनातून संपूर्ण झाडाचे पार करतो.

हे सुद्धा पहा
स्टॉक विकत घेण्यासाठी आणि विक्री करण्याचा उत्तम वेळ

स्पेस कॉम्प्लेक्सिटी

ओ (1) मॉरिस इनऑर्डर ट्रॅव्हर्सल वापरुन. रिकर्सिव्ह पध्दत घेईल ओ (एन) स्मृतीत जागा.