เส้นผ่านศูนย์กลางต้นไม้แบบทวิภาค (Diameter of Binary Tree) O(n) ใน C++

แนวคิด

เส้นผ่านศูนย์กลาง = left_height + right_height + 1 สำหรับแต่ละโหนด คำนวณความสูงและอัปเดตเส้นผ่านศูนย์กลางพร้อมกันใน O(n)

โครงสร้างโหนด

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

ฟังก์ชันคำนวณ

int height(Node* root, int& ans) {
    if (!root) return 0;
    int lh = height(root->left, ans);
    int rh = height(root->right, ans);
    ans = max(ans, 1 + lh + rh);  // อัปเดต diameter
    return 1 + max(lh, rh);       // ส่งคืนความสูง
}

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

โปรแกรมเต็ม

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

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

int height(Node* root, int& ans) {
    if (!root) return 0;
    int lh = height(root->left, ans);
    int rh = height(root->right, ans);
    ans = max(ans, 1 + lh + rh);
    return 1 + max(lh, rh);
}

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

int main() {
    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);
    cout << "Diameter is " << diameter(root);
    return 0;
}

ผลลัพธ์

Diameter is 4