สมมติว่าเรามีต้นไม้ไบนารีที่มีโหนดรูทและลูกด้านซ้ายและลูกด้านขวา ภารกิจคือการหาผลรวมของโหนดปลายสุดของต้นไม้ซึ่งเหลือไว้ที่โหนดหลัก
ตัวอย่าง
อินพุต-1:
ผลลัพธ์:
15
คำอธิบาย: ในไบนารีทรีอินพุตที่กำหนด ผลรวมของลีฟโหนดด้านซ้ายทั้งหมดคือ 9+4+2 =15 ดังนั้น เอาต์พุตคือ 15
แนวทางในการแก้ปัญหานี้
เรามี Binary Tree และภารกิจคือการหาผลรวมของ leaf nodes ทั้งหมดที่เหลืออยู่ใน parent.
วิธีการแบบเรียกซ้ำในการแก้ปัญหานี้คือตรวจสอบว่าโหนดด้านซ้ายของโหนดรากว่างเปล่าหรือไม่ หากว่างเปล่า ให้คำนวณผลรวมสำหรับโหนดด้านซ้ายและค้นหาผลรวมแบบเรียกซ้ำสำหรับโหนดด้านขวา ดังนั้น สำหรับทุกโหนด เราจะตรวจสอบซ้ำๆ และหาผลรวมของโหนดนั้น
- นำ Binary Tree ที่มีโหนดรูทและลูกด้านซ้ายและชายด์ด้านขวาเป็นอินพุต
- ฟังก์ชันจำนวนเต็ม leftLeafSum(treenode*root) รับโหนดรูทเป็นอินพุตและส่งกลับผลรวมของลีฟโหนดทั้งหมดที่เหลือให้พาเรนต์
- หากโหนดรูทว่างเปล่าหรือเป็น NULL ให้คืนค่า 'ศูนย์' มิฉะนั้น ให้ตรวจสอบโหนดด้านซ้ายของโหนดรูท
- หากโหนดด้านซ้ายของโหนดรากไม่มีลูก ให้ตรวจสอบโหนดที่ถูกต้องซ้ำๆ
- คืนค่าผลรวมแบบวนซ้ำสำหรับเด็กด้านซ้ายและชายที่ถูกต้อง
ตัวอย่าง
#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;
} การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น
ผลลัพธ์
10
คำอธิบาย: โหนดปลายสุดในโหนดด้านซ้ายคือ 5 และ 5 ซึ่งเหลือไว้ให้แม่ ดังนั้นผลรวมของโหนดปลายสุดคือ =10
