Сума левых лістоў рашэнняў Leetcode  


Узровень складанасці Лёгка
Часта пытаюцца ў Саман
алгарытмы кадаваньне інтэрв'ю інтэрв'юп LeetCode LeetCodeSolutions дрэва Абход дрэва

У гэтай задачы мы павінны знайсці суму ўсіх пакінутых лісця ў двайковай сістэме дрэва. Ліст, які называецца «Левы лісток”, Калі гэта левы даччыны які-небудзь вузел у дрэве.

Сума левых лістоў рашэнняў LeetcodePin

Прыклад    

     2
        
  /     \

4          7

        /      \

      9          4
Sum is 13
2

  \
 
    3
Sum is 0

Падыход  

Мы можам выкарыстоўваць рэкурсію для пераходу бінарнага дрэва. Калі ў якім-небудзь вузле ёсць левы дзіця, і гэта таксама лісток, мы можам дадаць значэнне левага дзіцяці да нашай сумы. Але гэты падыход выкарыстоўвае рэкурсіўную прастору стэка.

Ці можам мы выкарыстаць якую-небудзь іншую развязку, якая можа зэканоміць месца ў памяці?

Абход Морыса ў парадку можа быць рэалізавана для наведвання кожнага вузла ітэратыўна. Праверце, ці няма ў яго левага ліста, і ў выніку дадайце яго значэнне. Гэта аптымальны падыход. Звярніце ўвагу, што мы можам рэалізаваць "абход Морыса Inorder", толькі калі праблема дазваляе нам змяніць структуру дрэва.

Алгарытм (рэкурсіўны)  

  1. Стварыце функцыю sumOfLeftLeaves () які вяртае суму пакінутых лістоў любога пройдзенага корань
  2. Калі корань дрэва NULL
    • вярнуць нуль
  3. Калі ў бягучага кораня ёсць левы дзіця, і гэта а ліст
    • вярнуць яго значэнне + sumOfLeftLEaves (корань-> злева) + sumOfLeftLeaves (корань-> справа)
  4. Вярнуць sumOfLeftLEaves (корань-> злева) + sumOfLeftLeaves (корань-> справа)
Глядзіце таксама
Знайдзіце пераможцу на гульні Tic Tac Toe Leetcode Solution

Алгарытм (Морыс у парадку)  

  1. Пераход па двайковым файле з дапамогай Morris Inorder Traversal:
    • Навядзіце сабе папярэдніка inorder левага паддрэва любога вузла.
    • Калі нітка ўжо ёсць, развяжыце яе, каб захаваць першапачатковую структуру дрэва.
  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) з выкарыстаннем Morris Inorder Traversal. Патрэбен бы рэкурсіўны падыход O (N) прастору ў памяці.