סכום פתרונות Leetcode עלים שמאל


רמת קושי קַל
נשאל לעתים קרובות Adobe
עֵץ מעבר עץ

בבעיה זו עלינו למצוא את סכום כל העלים שנותרו בבינארי עץ. עלה המכונה "עלה שמאל”אם זה ילד שמאל של צומת כלשהו בעץ.

סכום פתרונות Leetcode עלים שמאל

דוגמה  

     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. הדפיס את התוצאה.

יישום

תוכנית C ++ של סכום פתרונות Leetcode עלים שמאליים

גישה רקורסיבית

#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 של סכום פתרונות Leetcode עלים שמאליים

גישה רקורסיבית

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

ניתוח מורכבות של סכום פתרונות Leetcode עלים שמאליים

מורכבות זמן

O (N) כשאנחנו חוצים את העץ כולו פעם אחת בגישה רקורסיבית ואיטראטיבית.

מורכבות בחלל

O (1) באמצעות מעבר מוריס. הגישה הרקורסיבית תנקוט עַל) מקום בזיכרון.