Đường kính cây nhị phân O(N) - Phương pháp mới trong C++

Đường kính (Diameter) của cây nhị phân là số lượng nút lớn nhất trên đường đi giữa hai nút lá bất kỳ. Công thức tại một nút: Đường kính qua nút = Chiều cao trái + Chiều cao phải + 1.

Phương pháp truyền thống tính chiều cao riêng rồi tính đường kính -> O(N²). Phương pháp **O(N) đơn pass** tính chiều cao và cập nhật đường kính tối đa cùng lúc trong một lần duyệt DFS (Post-order).

Thuật toán (DFS Post-order)

1. Hàm `height(node, &ans)` trả về chiều cao của cây con gốc `node`.
2. Tại mỗi nút: Tính `leftH = height(left)`, `rightH = height(right)`.
3. Cập nhật `ans = max(ans, leftH + rightH + 1)`.
4. Trả về `max(leftH, rightH) + 1` cho nút cha.

Chương trình C++ Hoàn chỉnh

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

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

// Trả về chiều cao, cập nhật ans qua tham chiếu
int heightAndDiameter(Node* root, int &ans) {
    if (!root) return 0;
    
    int leftH = heightAndDiameter(root->left, ans);
    int rightH = heightAndDiameter(root->right, ans);
    
    // Cập nhật đường kính lớn nhất thấy được
    ans = max(ans, leftH + rightH + 1);
    
    // Trả về chiều cao của cây con này
    return max(leftH, rightH) + 1;
}

int diameter(Node* root) {
    if (!root) return 0;
    int ans = INT_MIN;
    heightAndDiameter(root, ans);
    return ans;
}

// Helper tạo cây test
Node* buildSampleTree() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    // Đường kính: 4-2-1-3 (4 nodes) hoặc 5-2-1-3 (4 nodes)
    return root;
}

int main() {
    Node* root = buildSampleTree();
    cout << "Duong kinh cay nhi phan: " << diameter(root) << endl; // Output: 4
    return 0;
}

Đầu ra

Duong kinh cay nhi phan: 4

Độ phức tạp: Thời gian O(N) - duyệt mỗi nút 1 lần. Bộ nhớ O(H) - stack đệ quy (H = chiều cao cây).