Збир Леетцоде решења Леетцоде


Ниво тешкоће Лако
Често питани у адобе
Дрво Прелазак дрвета

У овом проблему морамо пронаћи збир свих левих листова у бинарном систему дрво. Лист који се назива „Леви лист”Ако је лево дете било ког чвора на дрвету.

Збир Леетцоде решења Леетцоде

Пример  

     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) користећи Моррис Инордер Траверсал. Рекурзивни приступ би био потребан НА) простора у сећању.