बाँया पातहरूको लेटकोड समाधानहरूको योग


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब
ट्री रूख ट्राभर्सल

यो समस्यामा, हामीले बाइनरीमा सबै बाँया पातहरूको योग भेट्टाउनु पर्छ रूख। पात भनिन्छ जुन "बाँया पात"यदि यो रूखमा कुनै नोडको बायाँ बच्चा हो।

बाँया पातहरूको लेटकोड समाधानहरूको योग

उदाहरणका  

     2
        
  /     \

4          7

        /      \

      9          4
Sum is 13
2

  \
 
    3
Sum is 0

दृष्टिकोण

बाइनरी रूखलाई पार गर्न हामी पुनरावृत्ति प्रयोग गर्न सक्छौं। यदि कुनै नोडको बायाँ बच्चा छ र यो पनि पात हो भने, हामी हाम्रो योगमा बायाँ बच्चाको मान थप्न सक्छौं। तर यस दृष्टिकोणले रिकर्सिभ स्ट्याक स्पेस प्रयोग गर्दछ।

के हामी कुनै पनि अन्य traversal प्रयोग गर्न सक्दछौं जसले मेमोरी स्पेस बचत गर्न सक्दछ?

मोरिस आन्तरिक ट्रैभर्सल प्रत्येक नोडलाई पुनरावृत्ति रूपमा भ्रमण गर्न लागू गर्न सकिन्छ। जाँच गर्नुहोस् कि यदि यसमा बायाँ पात बच्चा छ र परिणाममा यसको मूल्य सोही अनुसार थप्नुहोस्। यो इष्टतम दृष्टिकोण हो। नोट गर्नुहोस् कि यदि हामी समस्याले रूखको संरचना बदल्न अनुमति दियौं भने मात्र हामी "मोरिस ईन्टर ट्र्यावर्सल" लागू गर्न सक्दछौं।

एल्गोरिथ्म (रिकर्सिभ)

  1. प्रकार्य सिर्जना गर्नुहोस् SumOfLeftLeaves () जुन कुनै पनि पारित बायाँ पातहरूको योग फर्काउँछ मूल
  2. यदि रूखको जरा छ भने खाली
    • शून्य फिर्ता
  3. यदि हालको मूलको बायाँ बच्चा छ र यो हो पत्ता
    • यसको मान + SumOfLeftLEaves (root-> बायाँ) फर्काउनुहोस् + SumOfLeftLeaves (root-> दायाँ)
  4. फर्कनुहोस् SumOfLeftLEaves (root-> बायाँ) + SumOfLeftLeaves (मूल-> दायाँ)

एल्गोरिदम (मोरिस ईन्डर)

  1. बाउन्सरीलाई मोरिस ईन्टोर ट्र्याभर्सल प्रयोग गरी ट्राभर्स गर्नुहोस्:
    • आफैंमा कुनै नोडको बायाँ সাবट्रीको ईनर्डर पूर्ववर्ती थ्रेड गर्नुहोस्।
    • यदि एउटा थ्रेड पहिले नै अवस्थित छ भने, रूखको मूल संरचना कायम राख्न यसलाई अपठित गर्नुहोस्।
  2. यदि कुनै नोडको बायाँ बच्चा पात हो भने, यसलाई परिणाममा थप्नुहोस्।
  3. परिणाम प्रिन्ट गर्नुहोस्।

कार्यान्वयन

C ++ Lefcode समाधानहरूको योगको योग

रिकर्सिव दृष्टिकोण

#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

बाँया पातहरूको लेटकोड समाधानहरूको योगको जटिलता विश्लेषण

समय जटिलता

O (N), जस्तो कि हामी सबै रूखहरू एक पटक दुबै पुनरावृत्ति र पुनरावृत्ति दृष्टिकोणमा पार गर्दछौं।

ठाउँ जटिलता

O (१) मोरिस ईन्टर ट्रभर्सल प्रयोग गर्दै। रिकर्सिव दृष्टिकोण लिने थियो O (N) मेमोरीमा खाली ठाउँ.