Duyệt chéo (Diagonal Traversal) cây nhị phân trong C++

Duyệt chéo (Diagonal Traversal) của cây nhị phân: Xét các đường chéo có độ dốc -1 (xuống trái). Các nút nằm trên cùng một đường chéo này sẽ được nhóm lại và in ra theo thứ tự từ đường chéo gốc (root) ra ngoài.

Quy tắc xác định đường chéo (Diagonal Distance):

• Gốc (Root) ở đường chéo 0.
• Con trái: Tăng khoảng cách chéo +1.
• Con phải: Giữ nguyên khoảng cách chéo.

Ví dụ

Cây:
10
/ \
5 15
/ \ \
4 6 17
/
16

Kết quả duyệt chéo:
Đường chéo 0: 10 15 17
Đường chéo 1: 5 6 16
Đường chéo 2: 4

Phương pháp giải - Map + DFS

Dùng `map>` để lưu các nút theo `diagonal_distance`. Duyệt DFS (Pre-order hoặc In-order), cập nhật map. Cuối cùng in map theo key tăng dần.

Chương trình C++

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

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

void diagonalTraversalUtil(Node* root, int d, map<int, vector<int>> &diagMap) {
    if (!root) return;
    
    // Thêm nút hiện tại vào vector của đường chéo d
    diagMap[d].push_back(root->data);
    
    // Con trái -> đường chéo tiếp theo (d+1)
    diagonalTraversalUtil(root->left, d + 1, diagMap);
    // Con phải -> cùng đường chéo (d)
    diagonalTraversalUtil(root->right, d, diagMap);
}

void printDiagonalTraversal(Node* root) {
    map<int, vector<int>> diagMap;
    diagonalTraversalUtil(root, 0, diagMap);
    
    cout << "Duyet cheo (Diagonal Traversal):\n";
    for (auto &p : diagMap) {
        cout << "Duong cheo " << p.first << ": ";
        for (int val : p.second) cout << val << " ";
        cout << endl;
    }
}

int main() {
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    root->left->left = new Node(4);
    root->left->right = new Node(6);
    root->right->right = new Node(17);
    root->right->right->left = new Node(16);
    
    printDiagonalTraversal(root);
    return 0;
}

Đầu ra

Duyet cheo (Diagonal Traversal):
Duong cheo 0: 10 15 17
Duong cheo 1: 5 6 16
Duong cheo 2: 4