ในปัญหานี้ เราได้รับไบนารีทรีที่ประกอบด้วยจำนวนบวก งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดจากทรีที่มีระดับที่อยู่ติดกันไม่ได้รับอนุญาตใน C ++
คำอธิบายโค้ด
ที่นี่ เราจะพบผลรวมสูงสุดของโหนดของต้นไม้ในลักษณะที่ผลรวมไม่มีโหนดจากสองระดับที่อยู่ติดกันของต้นไม้
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ผลลัพธ์
21
คำอธิบาย
การรูทเป็นระดับเริ่มต้น ผลรวม =5 + 3 + 8 + 1 =17 การรูทย่อยของรูทเป็นระดับเริ่มต้น ผลรวม =2 + 6 + 9 + 4 =21
แนวทางการแก้ปัญหา
หากต้องการหา maxSum เงื่อนไขหนึ่งคือไม่มีองค์ประกอบที่อยู่ติดกัน สำหรับสิ่งนี้ เราจะนำชุดผลรวมหนึ่งชุดจากโหนดรูท (ระดับ 1) และอีกชุดหนึ่งจากโหนดย่อย (ระดับ 2) ผลรวมโหนดถัดไปจะถูกดึงออกจากโหนดปัจจุบันโดยการค้นหาโหนดหลาน
สำหรับสิ่งนี้ เราจะค้นหาค่า maxSum ซ้ำๆ จากนั้นค่าผลรวมสูงสุดสำหรับผลรวมที่เริ่มต้นจากระดับ 1 หรือระดับ 2 จะเป็นผลลัพธ์ maxSum
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* left, *right;
Node(int item){
data = item;
}
};
int getMaxSum(Node* root) ;
int findSumFromNode(Node* root){
if (root == NULL)
return 0;
int sum = root->data;
if (root->left != NULL){
sum += getMaxSum(root->left->left);
sum += getMaxSum(root->left->right);
}
if (root->right != NULL){
sum += getMaxSum(root->right->left);
sum += getMaxSum(root->right->right);
}
return sum;
}
int getMaxSum(Node* root){
if (root == NULL)
return 0;
return max(findSumFromNode(root), (findSumFromNode(root->left) + findSumFromNode(root->right)));
}
int main(){
Node* root = new Node(5);
root->left = new Node(2);
root->right = new Node(10);
root->left->left = new Node(4);
root->left->right = new Node(6);
root->right->right = new Node(9);
cout<<"The maximum sum from a tree with adjacent levels not allowed is "<<getMaxSum(root);
return 0;
} ผลลัพธ์
The maximum sum from a tree with adjacent levels not allowed is 24
