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.
Mündəricat
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)
- Bir funksiya yaradın sumOfLeftLeaves () keçən hər hansı birinin sol yarpaqlarının cəmini qaytaran kök
- Ağacın kökü varsa NULL
- sıfır qayıt
- 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ğ)
- SumOfLeftLEaves (kök-> sol) + sumOfLeftLeaves (kök-> sağ) qayıdın
Alqoritm (Morris İnorder)
- 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.
- Hər hansı bir düyünün sol uşağı bir yarpaqdırsa, nəticəyə əlavə edin.
- 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.
