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


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

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

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

Прыклад  

     2
        
  /     \

4          7

        /      \

      9          4
Sum is 13
2

  \
 
    3
Sum is 0

Падыход

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

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

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

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

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

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

  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) прастору ў памяці.