ผลรวมสูงสุดจากต้นไม้ที่ห้ามเลือกระดับติดกันใน C++

คำอธิบายโค้ด

ในที่นี้ เราจะหาผลรวมสูงสุดของโหนดในต้นไม้ โดยที่ผลรวมไม่ควรมีโหนดจากสองระดับที่ติดกันของต้นไม้

ตัวอย่างเพื่อความเข้าใจ:

เอาต์พุต

21

คำอธิบาย

ถ้าเริ่มจากราก (ระดับ 1) ผลรวม = 5 + 3 + 8 + 1 = 17
ถ้าเริ่มจากลูกของราก (ระดับ 2) ผลรวม = 2 + 6 + 9 + 4 = 21

แนวทางแก้ปัญหา

เพื่อหาผลรวมสูงสุด มีเงื่อนไขว่าไม่มีองค์ประกอบติดกัน สำหรับสิ่งนี้ เราจะเลือกชุดผลรวมหนึ่งจากโหนดราก (ระดับ 1) และอีกชุดจากโหนดลูก (ระดับ 2) โหนดผลรวมถัดไปจะถูกดึงออกมาจากโหนดปัจจุบันโดยการหาโหนดหลาน

สำหรับสิ่งนี้ เราจะหาค่า maxSum แบบเรียกซ้ำ (recursive) แล้วค่าผลรวมสูงสุดที่เริ่มจากระดับ 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