Ҷамъи баргҳои чапи Solutions Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Adobe
Дарахт Траверсал дарахт

Дар ин масъала, мо бояд ҷамъи ҳама баргҳои чапро дар дуӣ пайдо кунем дарахт. Барге, ки "Барги чап”Агар ин фарзанди чапи ягон гиреҳи дарахт бошад.

Ҷамъи баргҳои чапи Solutions Leetcode

мисол  

     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-> left) + sumOfLeftLeaves (root-> right)

Алгоритм (Моррис Инордер)

  1. Бо истифода аз Morris Inorder Traversal бинарро убур кунед:
    • Пешгузаштаи хатти зердарахти чапи ягон гиреҳро ба худ решакан кунед.
    • Агар ришта аллакай мавҷуд бошад, онро нигоҳ доред, то сохтори аслии дарахтро нигоҳ дорад.
  2. Агар кӯдаки чапи ягон гиреҳ барге бошад, онро ба натиҷа илова кунед.
  3. Натиҷаро чоп кунед.

татбиќи

C ++ Барномаи ҷамъбасти Leafcode Solutions

Усули рекурсивӣ

#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 аз миқдори Leafcode Solutions

Усули рекурсивӣ

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), чунон ки мо тамоми дарахтро як маротиба ҳам бо усули рекурсивӣ ва ҳам такрорӣ мегузарем.

Мураккабии фазо

О (1) бо истифода аз Моррис Инерасравс. Усули рекурсивӣ пешбинӣ шудааст О (Н) ҷой дар хотира.