ఎడమ ఆకుల మొత్తం లీట్‌కోడ్ సొల్యూషన్స్


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe
ట్రీ చెట్టు ట్రావెర్సల్

ఈ సమస్యలో, బైనరీలో అన్ని ఎడమ ఆకుల మొత్తాన్ని మనం కనుగొనాలి చెట్టు. “అని పిలువబడే ఆకుఎడమ ఆకు”అది చెట్టులోని ఏదైనా నోడ్ యొక్క ఎడమ బిడ్డ అయితే.

ఎడమ ఆకుల మొత్తం లీట్‌కోడ్ సొల్యూషన్స్

ఉదాహరణ  

     2
        
  /     \

4          7

        /      \

      9          4
Sum is 13
2

  \
 
    3
Sum is 0

అప్రోచ్

బైనరీ చెట్టును దాటడానికి మేము పునరావృత్తిని ఉపయోగించవచ్చు. ఏదైనా నోడ్‌లో ఎడమ బిడ్డ ఉంటే అది కూడా ఒక ఆకు అయితే, ఎడమ పిల్లల విలువను మన మొత్తానికి జోడించవచ్చు. కానీ ఈ విధానం పునరావృత స్టాక్ స్థలాన్ని ఉపయోగిస్తుంది.

మెమరీ స్థలాన్ని ఆదా చేయగల ఇతర ట్రావెర్సల్‌ను మనం ఉపయోగించవచ్చా?

మోరిస్ ఇనార్డర్ ట్రావెర్సల్ ప్రతి నోడ్‌ను పునరావృతంగా సందర్శించడానికి అమలు చేయవచ్చు. ఇది ఎడమ ఆకు పిల్లవాడిని కలిగి ఉందో లేదో తనిఖీ చేయండి మరియు దాని విలువను దాని ఫలితాన్ని జోడించండి. ఇది సరైన విధానం. చెట్టు యొక్క నిర్మాణాన్ని మార్చడానికి సమస్య అనుమతించినట్లయితే మాత్రమే మేము “మోరిస్ ఇనార్డర్ ట్రావెర్సల్” ను అమలు చేయగలమని గమనించండి.

అల్గోరిథం (పునరావృత)

  1. ఒక ఫంక్షన్ సృష్టించండి sumOfLeftLeaves () ఆమోదించిన ఎడమ ఆకుల మొత్తాన్ని తిరిగి ఇస్తుంది రూట్
  2. చెట్టు యొక్క మూలం ఉంటే NULL
    • తిరిగి సున్నా
  3. ప్రస్తుత మూలానికి ఎడమ బిడ్డ ఉంటే అది a ఆకు
    • దాని విలువను తిరిగి ఇవ్వండి + sumOfLeftLEaves (root-> left) + sumOfLeftLeaves (root-> right)
  4. SumOfLeftLEaves (root-> left) + sumOfLeftLeaves (root-> right)

అల్గోరిథం (మోరిస్ ఇనార్డర్)

  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

ఎడమ ఆకుల మొత్తం యొక్క సంక్లిష్టత విశ్లేషణ లీట్‌కోడ్ సొల్యూషన్స్

సమయం సంక్లిష్టత

పై), మేము మొత్తం చెట్టును పునరావృత మరియు పునరావృత విధానంలో ఒకసారి ప్రయాణిస్తున్నప్పుడు.

అంతరిక్ష సంక్లిష్టత

O (1) మోరిస్ ఇనార్డర్ ట్రావెర్సల్ ఉపయోగించి. పునరావృత విధానం పడుతుంది పై) మెమరీలో స్థలం.