หาผลรวมซับต้นไม้ที่มากที่สุดใน Binary Tree ใน C++

โจทย์

ได้รับ Binary Tree ที่มีค่าบวกและลบ ทางเราต้อง หาผลรวมของซับต้นไม้ (Subtree) ที่มีค่ามากที่สุด

ตัวอย่าง

Input: ต้นไม้ดังภาพ (รูท=5, ซ้าย=-4, ขวา=4, ...)

Output: 13

อธิบาย: ซับต้นไม้ซ้ายรวม=7, ขวา=1, ต้นไม้ทั้งหมด=13

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

ใช้ Post-order Traversal คำนวณผลรวมของซับต้นไม้ซ้ายและขวา แล้วเปรียบเทียบกับค่าสูงสุดที่พบจนถึงตอนนั้น

โปรแกรมตัวอย่าง

#include <iostream>
using namespace std;

struct Node { int key; Node *left, *right; };
Node* newNode(int key) { Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return temp; }

int calcSumTreeSumRec(Node* root, int& ans) {
    if (root == NULL) return 0;
    int currSum = root->key + calcSumTreeSumRec(root->left, ans) + calcSumTreeSumRec(root->right, ans);
    ans = max(ans, currSum);
    return currSum;
}

int calcMaxSubTreeSum(Node* root) {
    if (root == NULL) return 0;
    int ans = -100;
    calcSumTreeSumRec(root, ans);
    return ans;
}

int main() {
    Node* root = newNode(5);
    root->left = newNode(-4); root->right = newNode(4);
    root->left->left = newNode(3); root->left->right = newNode(8);
    root->right->left = newNode(-5); root->right->right = newNode(2);
    cout << "The largest subtree sum is " << calcMaxSubTreeSum(root);
    return 0;
}

ผลลัพธ์

The largest subtree sum is 13