Trong bài toán này, chúng ta được cho 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ả lá trái trong cây nhị phân cho trước.
Hãy xem ví dụ sau để hiểu bài toán:
Input : 
Output : 11
Giải thích −
Tất cả nút lá của cây là: 2, 9 Tổng = 2 + 9 = 11
Phương pháp giải
Một giải pháp đơn giản là duyệt cây từ gốc đến lá. Nếu một nút là lá trái, cộng vào tổng. Khi duyệt xong toàn bộ cây, in tổng.
Ví dụ
Chương trình minh họa cho giải pháp
#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; }Kết quả
The sum of left leaves of the tree is 11
Phương pháp khác sử dụng Lặp
Ta sẽ thực hiện duyệt theo chiều sâu trên cây, và kiểm tra nếu nút hiện tại là lá trái. Nếu có, cộng giá trị vào tổng, ngược lại bỏ qua. Cuối cùng in tổng.
Ví dụ
Chương trình minh họa cho giải pháp
#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; }Kết quả
The sum of left leaves of the tree is 11
Phương pháp 3, sử dụng BFS
Ta sẽ thực hiện tìm kiếm theo chiều rộng với biến chỉ ra nút có phải lá trái hay không. Nếu là, cộng vào tổng, ngược lại bỏ qua. Cuối cùng in tổng.
Ví dụ
Chương trình minh họa cho giải pháp
#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; }Kết quả
The sum of left leaves of the tree is 11