Tổng đường chéo (Diagonal Sum) cây nhị phân trong C++

Tổng đường chéo (Diagonal Sum) của cây nhị phân là tổng giá trị các nút nằm trên cùng một đường chéo (độ dốc -1). Tương tự duyệt chéo, nhưng thay vì lưu danh sách nút, ta cộng dồn tổng.

Phương pháp giải

Dùng `map` (hoặc `unordered_map`) lưu `diagonal_distance -> sum`. Duyệt DFS:

• Gốc: distance = 0.
• Con trái: distance + 1.
• Con phải: distance giữ nguyên.

Cập nhật: `map[d] += node->data`.

Chương trình C++

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

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

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

void printDiagonalSum(Node* root) {
    map<int, int> sumMap;
    diagonalSumUtil(root, 0, sumMap);
    
    cout << "Tong cac duong cheo (Diagonal Sums):\n";
    for (auto &p : sumMap) {
        cout << "Duong cheo " << p.first << ": " << p.second << endl;
    }
}

int main() {
    // Cây ví dụ
    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);
    /*
            1
          /   \
         2     3
        / \   / \
       9   6 4   5
        \  /  / \
        10 11 12 7
    */
    
    printDiagonalSum(root);
    return 0;
}

Đầu ra

Tong cac duong cheo (Diagonal Sums):
Duong cheo 0: 9
Duong cheo 1: 19
Duong cheo 2: 42

Giải thích: D0: 1+3+5=9. D1: 2+4+6+7=19. D2: 9+12+11+10=42. (Code gốc in "91942" do thiếu định dạng, đã sửa).