Giả sử chúng ta có Cây nhị phân có nút gốc và nút con bên trái và nút con bên phải của nó. Nhiệm vụ là tìm tổng số nút lá của cây được để lại cho nút cha của nó.
Ví dụ
Đầu vào-1:
Đầu ra:
15
Giải thích: Trong Cây nhị phân đầu vào đã cho, tổng của tất cả các nút lá bên trái là 9 + 4 + 2 =15. Vì vậy, đầu ra là 15.
Phương pháp tiếp cận để giải quyết vấn đề này
Chúng ta có Cây nhị phân và nhiệm vụ là tìm tổng của tất cả các nút lá được để lại cho nút cha của nó.
Cách tiếp cận đệ quy để giải quyết vấn đề này là kiểm tra xem nút bên trái của nút gốc có trống hay không. Nếu nó trống, sau đó tính tổng cho nút bên trái của nó và tìm tổng đệ quy cho nút bên phải. Do đó, đối với mọi nút, chúng tôi sẽ kiểm tra đệ quy và tìm tổng của nó.
- Lấy Cây nhị phân có các nút gốc và nút con bên trái cũng như nút con bên phải làm đầu vào.
- Một hàm số nguyên leftLeafSum (treenode * root) lấy nút gốc làm đầu vào và trả về tổng của tất cả các nút lá được để lại cho nút cha của nó.
- Nếu nút gốc trống hoặc NULL, hãy trả về 'không', nếu không hãy kiểm tra nút bên trái của nút gốc.
- Nếu nút bên trái của nút gốc không có nút con, thì hãy kiểm tra một cách đệ quy để tìm nút bên phải.
- Trả về tổng một cách đệ quy cho con bên trái và con bên phải.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
int leftLeafSum(treenode * root) {
if (root == NULL) {
return 0;
}
if (root -> left and!root -> left -> left and!root -> left -> right) {
return root -> left -> data + leftLeafSum(root -> right);
}
return leftLeafSum(root -> left) + leftLeafSum(root -> right);
}
int main() {
struct treenode * root = NULL;
root = createNode(4);
root -> left = createNode(2);
root -> right = createNode(2);
root -> left -> right = createNode(7);
root -> left -> left = createNode(5);
root -> right -> left = createNode(5);
root -> right -> right = createNode(7);
int sum = leftLeafSum(root);
cout << sum << endl;
return 0;
} Chạy đoạn mã trên sẽ tạo ra kết quả là,
Đầu ra
10
Giải thích: Các nút lá trong các nút bên trái là 5 và 5 được để lại cho nút cha của chúng, do đó tổng của tất cả các nút lá là =10.