Sol Leaves Leetcode Solutions cəmi

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions Ağac Ağacın keçidiBaxılıb 89

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Bu problemdə ikili ikiqat bütün sol yarpaqların cəmini tapmalıyıq ağac. “Adlanan bir yarpaqSol yarpaq”Ağacdakı hər hansı bir düyünün sol uşağıdırsa.

Sol Leaves Leetcode Solutions cəmiPin

misal  

     2
        
  /     \

4          7

        /      \

      9          4
Sum is 13
2

  \
 
    3
Sum is 0

Yanaşma

İkili ağacdan keçmək üçün rekursiyadan istifadə edə bilərik. Hər hansı bir düyünün sol uşağı varsa və bu da bir yarpaqdırsa, sol uşağın dəyərini cəmimizə əlavə edə bilərik. Ancaq bu yanaşma rekursiv yığın yerindən istifadə edir.

Yaddaş məkanını saxlaya biləcək başqa bir hərəkətdən istifadə edə bilərikmi?

Morris Inorder Traversal hər bir nodu təkrarən ziyarət etmək üçün həyata keçirilə bilər. Sol yarpaq uşağının olub olmadığını yoxlayın və nəticəyə görə dəyərini əlavə edin. Bu, optimal yanaşmadır. Qeyd edək ki, “Morris Inorder traversal” ı yalnız problem ağacın quruluşunu dəyişdirməyə imkan verdiyi təqdirdə həyata keçirə bilərik.

Alqoritm (Rekursiv)

  1. Bir funksiya yaradın sumOfLeftLeaves () keçən hər hansı birinin sol yarpaqlarının cəmini qaytaran kök
  2. Ağacın kökü varsa NULL
    • sıfır qayıt
  3. Mövcud kökün sol uşağı varsa və bu yarpaq
    • dəyərini qaytarın + sumOfLeftLEaves (kök-> sol) + sumOfLeftLeaves (kök-> sağ)
  4. SumOfLeftLEaves (kök-> sol) + sumOfLeftLeaves (kök-> sağ) qayıdın

Alqoritm (Morris İnorder)

  1. Morris Inorder Traversal istifadə edərək ikili keçid:
    • Hər hansı bir düyünün sol alt ağacının inorder sələfini özünə vurun.
    • Bir iplik onsuz da varsa, ağacın orijinal quruluşunu qorumaq üçün onu açın.
  2. Hər hansı bir düyünün sol uşağı bir yarpaqdırsa, nəticəyə əlavə edin.
  3. Nəticəni çap edin.

Həyata keçirilməsi

Sol Leaves Leetcode Solutions C ++ Proqramının Cəmi

Rekursiv yanaşma

#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;
}

Optimal metod

#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

Leafcode Solutions Leafcode Solutions cəminin Java Proqramı

Rekursiv yanaşma

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));
    }
}

Optimal metod

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

Sol yarpaqların cəmi Leetcode həllərinin mürəkkəbliyinin təhlili

Zamanın mürəkkəbliyi

O (N), həm rekursiv, həm də təkrarlanan yanaşmada bütün ağacdan bir dəfə keçdikdə.

Kosmik Mürəkkəblik

O (1) Morris Inorder Traversal istifadə. Rekursiv yanaşma olacaq O (N) yaddaşda yer.

Crack Sistemi Dizayn Müsahibələri
Translate »
1