ผลรวมแนวทแยงของต้นไม้แบบทวิภาค (Diagonal Sum) ใน C++

แนวคิด

Diagonal Sum: ผลรวมค่าของโหนดที่อยู่บนเส้นทแยงเดียวกัน (ความชัน -1)

อัลกอริธึม

• Map: Key = depth, Value = ผลรวมค่าโหนด
• Recursive traversal: ซ้าย depth+1, ขวา depth คงเดิม
• สะสมค่าใน map[depth]

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

#include <iostream>
#include <map>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

void diagonalSum(Node* root, int depth, map<int, int>& sumMap) {
    if (root) {
        sumMap[depth] += root->data;
        diagonalSum(root->left, depth + 1, sumMap);
        diagonalSum(root->right, depth, sumMap);
    }
}

int main() {
    Node* root = new Node(1);
    root->right = new Node(3);
    root->right->left = new Node(4);
    root->right->left->left = new Node(12);
    root->right->left->right = new Node(7);
    root->left = new Node(2);
    root->left->left = new Node(9);
    root->left->right = new Node(6);
    root->left->left->right = new Node(10);
    root->left->right->left = new Node(11);
    root->right->right = new Node(5);
    
    map<int, int> sumMap;
    diagonalSum(root, 1, sumMap);
    
    for (auto& p : sumMap)
        cout << p.second << "\t";
    return 0;
}

ผลลัพธ์

9 19 4 2