In nút lá tại level cho trước của cây nhị phân trong C

Bài toán

In các nút lá (leaf nodes: left=right=NULL) ở level k của cây nhị phân.

Ví dụ

Tree:
       11
      /  \
    22    33
   /       \
 66         44
 / \
88 77

Level 4: 88 77

Thuật toán đệ quy level-order

leaf(root, level):
    if !root: return
    if level==1:
        if !root->left && !root->right: print root->data
    else:
        leaf(root->left, level-1)
        leaf(root->right, level-1)

Mã nguồn C

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

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

struct node* New(int data) {
    struct node* n = malloc(sizeof(struct node));
    n->data = data; n->left = n->right = NULL; return n;
}

void leaf(struct node* root, int level) {
    if (!root) return;
    if (level == 1) {
        if (!root->left && !root->right) printf("%d\n", root->data);
    } else {
        leaf(root->left, level-1);
        leaf(root->right, level-1);
    }
}

int main() {
    struct node* root = New(11);
    root->left = New(22); root->right = New(33);
    root->left->left = New(66); root->right->right = New(44);
    root->left->left->left = New(88);
    root->left->left->right = New(77);
    leaf(root, 4);
    return 0;
}

Kết quả

88
77