Trong bài toán này, chúng ta được đưa ra một cây nhị phân. Nhiệm vụ của chúng ta là tìm tổng của tất cả các lá còn lại trong Cây nhị phân đã cho .
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào :
Đầu ra:11
Giải thích -
All leaf nodes of the tree are : 2, 9 Sum = 2 + 9 = 11
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề này là cắt ngang cây từ gốc đến lá. Nếu một nút là nút lá bên trái, hãy cộng nó thành tổng. Khi toàn bộ cây được đi ngang. In Tổng.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <iostream>
using namespace std;
struct Node{
int key;
struct Node* left, *right;
};
Node *newNode(char k){
Node *node = new Node;
node->key = k;
node->right = node->left = NULL;
return node;
}
bool isLeafNode(Node *node){
if (node == NULL)
return false;
if (node->left == NULL && node->right == NULL)
return true;
return false;
}
int findLeftLeavesSum(Node *root){
int sum = 0;
if (root != NULL){
if (isLeafNode(root->left))
sum += root->left->key;
else
sum += findLeftLeavesSum(root->left);
sum += findLeftLeavesSum(root->right);
}
return sum;
}
int main(){
struct Node *root = newNode(5);
root->left = newNode(4);
root->right = newNode(6);
root->left->left = newNode(2);
root->left->right = newNode(1);
root->right->left = newNode(9);
root->right->right = newNode(7);
cout<<"The sum of left leaves of the tree is "<<findLeftLeavesSum(root);
return 0;
} Đầu ra
The sum of left leaves of the tree is 11
Một cách tiếp cận khác sử dụng Lặp lại
Chúng tôi sẽ thực hiện tìm kiếm theo chiều sâu đầu tiên trên cây, và sau đó kiểm tra xem nút hiện tại có phải là lá bên trái hay không. Nếu Có, hãy cộng giá trị của nó thành tổng, nếu không, bỏ đi. Ở cuối, hãy in tổng.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include<bits/stdc++.h>
using namespace std;
struct Node{
int key;
struct Node* left, *right;
};
Node *newNode(char k){
Node *node = new Node;
node->key = k;
node->right = node->left = NULL;
return node;
}
int findLeftLeavesSum(Node* root){
if(root == NULL)
return 0;
stack<Node*> treeNodes;
treeNodes.push(root);
int sum = 0;
while(treeNodes.size() > 0){
Node* currentNode = treeNodes.top();
treeNodes.pop();
if (currentNode->left != NULL){
treeNodes.push(currentNode->left);
if(currentNode->left->left == NULL &&
currentNode->left->right == NULL){
sum += currentNode->left->key ;
}
}
if (currentNode->right != NULL)
treeNodes.push(currentNode->right);
}
return sum;
}
int main(){
Node *root = newNode(5);
root->left= newNode(4);
root->right = newNode(6);
root->left->left = newNode(2);
root->left->right = newNode(1);
root->right->left = newNode(9);
root->right->right= newNode(7);
cout<<"The sum of left leaves of the tree is "<<findLeftLeavesSum(root);
return 0;
} Đầu ra
The sum of left leaves of the tree is 11
Phương pháp tiếp cận 3, sử dụng BFS
Chúng tôi sẽ thực hiện tìm kiếm theo chiều rộng đầu tiên với một biến để cho biết liệu nút có phải là nút con bên trái hay không. Nếu đúng, hãy cộng nó vào tổng, nếu không thì bỏ đi. Ở cuối, in tổng.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include<bits/stdc++.h>
using namespace std;
struct Node{
int key; struct Node* left, *right;
};
Node *newNode(char k){
Node *node = new Node;
node->key = k;
node->right = node->left = NULL;
return node;
}
int findLeftLeavesSum(Node* root) {
if (root == NULL)
return 0;
queue<pair<Node*, bool> > leftTreeNodes;
leftTreeNodes.push({ root, 0 });
int sum = 0;
while (!leftTreeNodes.empty()) {
Node* temp = leftTreeNodes.front().first;
bool is_left_child = leftTreeNodes.front().second;
leftTreeNodes.pop();
if (!temp->left && !temp->right && is_left_child)
sum = sum + temp->key;
if (temp->left) {
leftTreeNodes.push({ temp->left, 1 });
}
if (temp->right) {
leftTreeNodes.push({ temp->right, 0 });
}
}
return sum;
}
int main(){
Node *root = newNode(5);
root->left= newNode(4);
root->right = newNode(6);
root->left->left = newNode(2);
root->left->right = newNode(1);
root->right->left = newNode(9);
root->right->right= newNode(7);
cout<<"The sum of left leaves of the tree is "<<findLeftLeavesSum(root);
return 0;
} Đầu ra
The sum of left leaves of the tree is 11