ในปัญหานี้ เราได้รับไบนารีทรีโดยแต่ละโหนดมีค่า งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมเส้นทางสูงสุดระหว่างสองใบของไบนารีทรี
ที่นี่ เราต้องหาเส้นทางจากโหนดปลายหนึ่งไปยังโหนดปลายสุดอื่นที่จะให้ผลรวมของค่าสูงสุด เส้นทางผลรวมสูงสุดนี้สามารถ/ไม่สามารถรวมโหนดรูทได้
ต้นไม้ไบนารี เป็นโครงสร้างข้อมูลแบบต้นไม้ซึ่งแต่ละโหนดสามารถมีโหนดย่อยได้สูงสุดสองโหนด สิ่งเหล่านี้เรียกว่าลูกซ้ายและขวา
ตัวอย่าง −
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −
ป้อนข้อมูล − //ไบนารีทรี…
ผลผลิต − 24
คำอธิบาย − เส้นทางจากโหนดปลายเท้า − 2 ถึง 9 จะให้ผลรวมสูงสุดคือ (2 + 5 + 6 -2 + 4 + 9 ) =24
เพื่อแก้ปัญหานี้ เราจะทำการข้ามต้นไม้และเก็บผลรวมสูงสุดสำหรับทรีย่อยย่อยด้านซ้าย/ขวาสำหรับโหนดปัจจุบัน นอกจากนี้ เราจะพบเส้นทางสูงสุดระหว่างโหนดปลายทั้งสองจนถึงตอนนี้
สำหรับทุกๆ โหนด เราจะค้นหาเส้นทาง leaf to leaf สูงสุดที่เป็นไปได้สำหรับแผนผังย่อย จากนั้นเปรียบเทียบกับเส้นทางสูงสุดโดยรวมและเก็บค่าสูงสุดของทั้งสองค่าไว้ในค่าผลรวมของเส้นทางสูงสุดทั่วโลก
ลองดูวิธีแก้ปัญหานี้จากตัวอย่างของเราเพื่อทำความเข้าใจวิธีแก้ปัญหาให้ดีขึ้น -
ผลรวมสูงสุดทั่วโลก =6 (สำหรับเส้นทาง 2→5→-1)
ตอนนี้เราจะตรวจสอบเพื่อรับ 6 เป็นโหนดรูท
ในทรีย่อยด้านซ้าย −
ผลรวมของเส้นทางจนถึงโหนดปลายสุดคือ 7 และ 4
สูงสุดคือ 7 (สำหรับเส้นทาง 5→2)
ในทรีย่อยด้านขวา −
ผลรวมของเส้นทางจนถึงโหนดปลายสุดคือ 5 สำหรับเส้นทาง (1rarr;-3rarr;7) ซึ่งเป็นวิธีหนึ่งที่เป็นไปได้
ไม่ ผลรวมของเส้นทางระหว่างโหนดปลายสุดคือ −
ผลรวมสูงสุดของ leaf to root(6) ในทรีย่อยด้านซ้าย + root + ผลรวมสูงสุดของ leaf to root(6) ในทรีย่อยด้านขวา =7 + 6 + 5 =18.
เปรียบเทียบกับผลรวมเส้นทางสูงสุดทั่วโลก (6), ผลรวมเส้นทางสูงสุดทั่วโลกใหม่ =18
ตัวอย่าง
โปรแกรมค้นหาผลรวมเส้นทางสูงสุดระหว่างโหนดปลายทั้งสอง -
#include <bits/stdc++.h>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
struct Node* insertNode(int data){
struct Node* node = new(struct Node);
node->data = data;
node->left = node->right = NULL;
return (node);
}
int max(int a, int b)
{ return (a >= b)? a: b; }
int maxPathSumLeaf(struct Node *root, int &maxSum){
if (root==NULL) return 0;
if (!root->left && !root->right) return root->data;
int leftSubTree = maxPathSumLeaf(root->left, maxSum);
int rightSubTree = maxPathSumLeaf(root->right, maxSum);
if (root->left && root->right){
maxSum = max(maxSum, leftSubTree + rightSubTree + root->data);
return max(leftSubTree, rightSubTree) + root->data;
}
return (!root->left)? rightSubTree + root->data: leftSubTree + root->data;
}
int main(){
struct Node *root = insertNode(-2);
root->left = insertNode(6);
root->right = insertNode(4);
root->left->left = insertNode(5);
root->left->right = insertNode(1);
root->left->left->left = insertNode(2);
root->left->left->right = insertNode(-1);
root->left->right->left = insertNode(-3);
root->left->right->left->left = insertNode(7);
root->right->left = insertNode(9);
root->right->right = insertNode(3);
int maxSum = INT_MIN;
maxPathSumLeaf(root, maxSum);
cout<<"Max pathSum of between two leaf nodes for the given binary tree is "<<maxSum;
return 0;
} ผลลัพธ์
Max pathSum of between two leaf nodes for the given binary tree is 24
