लेफ्ट के लेफ्टकोड सॉल्यूशंस का योग


कठिनाई स्तर आसान
में अक्सर पूछा एडोब
पेड़ वृक्ष का त्राटक

इस समस्या में, हमें एक बाइनरी में सभी बाईं पत्तियों का योग ढूंढना होगा पेड़। एक पत्ता जिसे "कहा जाता है"पान का पत्ता“अगर यह पेड़ में किसी भी नोड का एक बचा हुआ बच्चा है।

लेफ्ट के लेफ्टकोड सॉल्यूशंस का योग

उदाहरण  

     2
        
  /     \

4          7

        /      \

      9          4
Sum is 13
2

  \
 
    3
Sum is 0

दृष्टिकोण

हम बाइनरी ट्री को पार करने के लिए पुनरावृत्ति का उपयोग कर सकते हैं। यदि किसी भी नोड में एक बाएं बच्चा है और यह एक पत्ती भी है, तो हम अपने योग के लिए बाएं बच्चे का मूल्य जोड़ सकते हैं। लेकिन यह दृष्टिकोण पुनरावर्ती स्टैक स्थान का उपयोग करता है।

क्या हम किसी अन्य ट्रैवर्सल का उपयोग कर सकते हैं जो मेमोरी स्पेस को बचा सकता है?

मॉरिस इनवर्टर ट्रैवर्सल हर नोड को यात्रा करने के लिए कार्यान्वित किया जा सकता है। जांचें कि क्या उसके पास एक पत्ती का बच्चा है और परिणाम के अनुसार उसका मूल्य जोड़ें। यह इष्टतम दृष्टिकोण है। ध्यान दें कि हम "मॉरिस इनवर्टर ट्रैवर्सल" को तभी लागू कर सकते हैं जब समस्या हमें पेड़ की संरचना को बदलने की अनुमति देती है।

एल्गोरिथम (पुनरावर्ती)

  1. एक फंक्शन बनाएं सारांश कि किसी भी पारित कर दिया के बाईं पत्तियों का योग देता है जड़
  2. अगर पेड़ की जड़ है नल
    • शून्य लौटाओ
  3. यदि वर्तमान जड़ में एक बाएं बच्चा है और यह ए है पत्ता
    • उसका मान लौटाएँ
  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) मॉरिस इनवर्टर ट्रैवर्सल का उपयोग करना। पुनरावर्ती दृष्टिकोण होगा पर) स्मृति में स्थान.