Chương trình C++ in đường đi lá đến lá dài nhất trong cây nhị phân

In đường đi dài nhất từ nút lá đến nút lá khác trong cây nhị phân. Tức là in tất cả nút trên đường kính (diameter) của cây.

Giải pháp: tính đường kính dùng hàm height. Tìm đường dài nhất bên trái và bên phải. In nút bên trái, gốc, nút bên phải.

Ví dụ mã nguồn

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
};

struct Node* create_node(int data) {
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

int tree_height(Node* root, int& ans, Node*(&k), int& lh, int& rh, int& f) {
    if (root == NULL)
        return 0;
    int left_tree_height = tree_height(root->left, ans, k, lh, rh, f);
    int right_tree_height = tree_height(root->right, ans, k, lh, rh, f);
    if (ans < 1 + left_tree_height + right_tree_height) {
        ans = 1 + left_tree_height + right_tree_height;
        k = root;
        lh = left_tree_height;
        rh = right_tree_height;
    }
    return 1 + max(left_tree_height, right_tree_height);
}

void print_roottonode(int ints[], int len, int f) {
    int i;
    if (f == 0) {
        for (i = len - 1; i >= 0; i--)
            printf("%d ", ints[i]);
    } else if (f == 1) {
        for (i = 0; i < len; i++)
            printf("%d ", ints[i]);
    }
}

void print_pathr(Node* node, int path[], int pathLen, int max, int& f) {
    if (node == NULL)
        return;
    path[pathLen] = node->data;
    pathLen++;
    if (node->left == NULL && node->right == NULL) {
        if (pathLen == max && (f == 0 || f == 1)) {
            print_roottonode(path, pathLen, f);
            f = 2;
        }
    } else {
        print_pathr(node->left, path, pathLen, max, f);
        print_pathr(node->right, path, pathLen, max, f);
    }
}

void calc_diameter(Node* root) {
    if (root == NULL)
        return;
    int ans = INT_MIN, lh = 0, rh = 0;
    int f = 0;
    Node* k;
    int tree_height_of_tree = tree_height(root, ans, k, lh, rh, f);
    int lPath[100], pathlen = 0;
    print_pathr(k->left, lPath, pathlen, lh, f);
    printf("%d ", k->data);
    int rPath[100];
    f = 1;
    print_pathr(k->right, rPath, pathlen, rh, f);
}

int main() {
    struct Node* root = create_node(12);
    root->left = create_node(22);
    root->right = create_node(33);
    root->left->left = create_node(45);
    root->left->right = create_node(57);
    root->left->right->left = create_node(26);
    root->left->right->right = create_node(76);
    root->left->left->right = create_node(84);
    root->left->left->right->left = create_node(97);
    calc_diameter(root);
    return 0;
}

Kết quả đầu ra

97 84 45 22 57 26