סאַכאַקל פון לעפט קאָוד סאַלושאַנז


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַדאָובי
בוים בוים טראַווערסאַל

אין דעם פּראָבלעם, מיר מוזן געפֿינען די סומע פון ​​אַלע לינקס בלעטער אין אַ ביינערי בוים. א בלאַט וואָס איז גערופן אַ "לינקס ליף”אויב עס איז אַ לינקס קינד פון קיין נאָדע אין דעם בוים.

סאַכאַקל פון לעפט קאָוד סאַלושאַנז

בייַשפּיל  

     2
        
  /     \

4          7

        /      \

      9          4
Sum is 13
2

  \
 
    3
Sum is 0

צוגאַנג

מיר קענען נוצן רעקורסיאָן דורך די ביינערי בוים. אויב קיין נאָדע האט אַ לינקס קינד און עס איז אויך אַ בלאַט, מיר קענען לייגן די ווערט פון די לינקס קינד צו אונדזער סומע. אבער דעם צוגאַנג ניצט די רעקורסיווע אָנלייגן פּלאַץ.

קענען מיר נוצן קיין אנדערע טראַווערסאַל וואָס קענען שפּאָרן די זכּרון פּלאַץ?

מאָריס ינאָרדער טראַווערסאַל קענען זיין ימפּלאַמענאַד צו באַזוכן יעדער נאָדע יטעראַטיוולי. קאָנטראָלירן אויב עס האט אַ לינקס בלאַט קינד און לייגן די ווערט אַקאָרדינגלי אין די רעזולטאַט. דאָס איז דער אָפּטימאַל צוגאַנג. באַמערקונג אַז מיר קענען מאַי "מאַריס ינאָרדער טראַווערסאַל" בלויז אויב די פּראָבלעם אַלאַוז אונדז צו טוישן די סטרוקטור פון דעם בוים.

אַלגערידאַם (רעקורסיווע)

  1. שאַפֿן אַ פֿונקציע sumOfLeftLeaves () וואָס קערט די סומע פון ​​לינקס בלעטער פון קיין דורכגעגאנגען וואָרצל
  2. אויב דער וואָרצל פון דעם בוים איז נאַל
    • צוריקקומען נול
  3. אויב די קראַנט שורש האט אַ לינקס קינד און עס איז אַ בלאַט
    • צוריקקומען זייַן ווערט + sumOfLeftLEaves (root-> left) + sumOfLeftLeaves (root-> right)
  4. צוריקקומען sumOfLeftLEaves (root-> לינקס) + sumOfLeftLeaves (root-> רעכט)

אַלגערידאַם (מאָריס ינאָרדער)

  1. אַריבער די ביינערי ניצן Morris Inorder Traversal:
    • פֿאָדעם די ינאָרדער פאָרויסגייער פון די לינקס סובטרעע פון ​​קיין נאָדע צו זיך.
    • אויב אַ פאָדעם איז שוין פאָרשטעלן, ונטרעאַד עס צו האַלטן דער אָריגינעל סטרוקטור פון דער בוים.
  2. אויב די לינקס קינד פון קיין נאָדע איז אַ בלאַט, לייג עס צו די רעזולטאַט.
  3. דרוק דעם רעזולטאַט.

ימפּלעמענטאַטיאָן

C ++ פּראָגראַם פון סומע פון ​​לעפט קאָוד סאַלושאַנז

רעקורסיווע צוגאַנג

#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

Java פּראָגראַם פֿאַר סומע פון ​​לעפט קאָוד סאַלושאַנז

רעקורסיווע צוגאַנג

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

קאַמפּלעקסיטי אַנאַליסיס פון די סומע פון ​​לעפט קאָדעקס סאַלושאַנז

צייט קאַמפּלעקסיטי

אָ (N), ווען מיר פאָרן די גאנצע בוים אַמאָל אין ביידע רעקורסיווע און יטעראַטיווע צוגאַנג.

ספעיס קאַמפּלעקסיטי

אָ (1) ניצן מאָריס ינאָרדער טראַווערסאַל. די רעקורסיווע צוגאַנג וואָלט נעמען אָ (N) פּלאַץ אין דער זכּרון.