Maximum Path Sum in Binary Tree: ผลรวมเส้นทางสูงสุดระหว่างใบสองใบใน C++

ปัญหา

กำหนด Binary Tree หา Maximum Path Sum ระหว่างใบ (Leaf) สองใบ เส้นทางอาจ/อาจไม่ผ่าน Root

ตัวอย่าง: Tree ด้านล่าง → Max Sum = 24 (Path: 2→5→6→-2→4→9)

แนวคิด: Post-order Traversal + Global Maximum

Recursive Function

maxPathSumLeaf(node, &maxSum) คืนค่า: Max Sum จาก Node นี้ลงใบใดใบหนึ่ง

Side effect: อัปเดต maxSum = Max Leaf-to-Leaf Path ที่เจอจนถึงตอนนี้

Logic

• Leaf: คืน node->data
• Internal Node:
  • Left Max = Recurse Left
  • Right Max = Recurse Right
  • ถ้ามีลูกทั้งคู่: maxSum = max(maxSum, left + right + node->data) (Leaf-to-Leaf ผ่าน Node นี้)
  • คืน max(left, right) + node->data (Max Single Path ขึ้นไป Parent)
• Single Child: คืน childMax + node->data

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
};

Node* newNode(int data) {
    Node* node = new Node();
    node->data = data;
    node->left = node->right = nullptr;
    return node;
}

int maxPathSumLeaf(Node* root, int& maxSum) {
    if (!root) return 0;
    if (!root->left && !root->right) return root->data;
    
    int leftSum = maxPathSumLeaf(root->left, maxSum);
    int rightSum = maxPathSumLeaf(root->right, maxSum);
    
    if (root->left && root->right) {
        // Leaf-to-Leaf through this node
        maxSum = max(maxSum, leftSum + rightSum + root->data);
        return max(leftSum, rightSum) + root->data;
    }
    
    return (!root->left) ? rightSum + root->data : leftSum + root->data;
}

int main() {
    Node* root = newNode(-2);
    root->left = newNode(6);
    root->right = newNode(4);
    root->left->left = newNode(5);
    root->left->right = newNode(1);
    root->left->left->left = newNode(2);
    root->left->left->right = newNode(-1);
    root->left->right->left = newNode(-3);
    root->left->right->left->left = newNode(7);
    root->right->left = newNode(9);
    root->right->right = newNode(3);
    
    int maxSum = INT_MIN;
    maxPathSumLeaf(root, maxSum);
    cout << "Max pathSum between two leaf nodes: " << maxSum;  // 24
    return 0;
}

Tree Diagram

        -2
       /  \
      6    4
     / \  / \
    5   1 9  3
   / \  /
  2  -1 -3
        /
       7

Trace Path (Sum = 24)

Leaf 2 → 5 → 6 → -2 → 4 → 9 (Leaf)
2 + 5 + 6 + (-2) + 4 + 9 = 24

ความซับซ้อน

• Time: O(n) - เยี่ยมทุกโหนด 1 ครั้ง
• Space: O(h) - Recursion Stack (h = Height)

Input / Output

Input:  Binary Tree as above
Output: Max pathSum between two leaf nodes for the given binary tree is 24