In level giữa của cây nhị phân hoàn hảo không cần tính chiều cao trong C

Bài toán

In các nút ở level giữa của perfect binary tree (cây nhị phân hoàn hảo: mọi nút nội có 2 con, lá cùng level) mà không tính height.

Ví dụ

Tree:
      13
    /    \
  21      44
 / \     / \
98 57  61  70

Middle level: 21 44

Ý tưởng

Giống tìm giữa linked list: dùng 2 con trỏ a, b. b đi nhanh gấp 2 (b->left->left). Khi b đến lá (left/right NULL), a đang ở level giữa.

Mã nguồn C

#include <stdio.h>
#include <stdlib.h>

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

struct Node* New(int v) {
    struct Node* n = malloc(sizeof(struct Node));
    n->key = v; n->left = n->right = NULL; return n;
}

void middle(struct Node* a, struct Node* b) {
    if (!a || !b) return;
    if (!b->left && !b->right) { printf("%d ", a->key); return; }
    middle(a->left, b->left->left);
    middle(a->right, b->left->left);
}

void mid_level(struct Node* root) { middle(root, root); }

int main() {
    struct Node* n1=New(13), *n2=New(21), *n3=New(44);
    struct Node* n4=New(98), *n5=New(57), *n6=New(61), *n7=New(70);
    n2->left=n4; n2->right=n5;
    n3->left=n6; n3->right=n7;
    n1->left=n2; n1->right=n3;
    printf("Middle level: "); mid_level(n1);
    return 0;
}

Kết quả

Middle level: 21 44