二叉搜索樹葉子節點深度計算：遞歸與迭代實現

獲取二叉搜索樹（BST）所有葉子節點的深度，是樹遍歷的基礎應用。本文提供遞歸、迭代、層序三種實現，並分析時空複雜度。

問題定義

• 葉子節點：無左、右子節點的節點
• 深度：根節點到該節點的邊數（根深度為 0）
• 輸出：所有葉子節點的深度列表或統計信息

遞歸實現（最直觀）

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

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

void leafDepthsRec(TreeNode *root, int depth, int **result, int *count, int *capacity) {
    if (!root) return;
    
    if (!root->left && !root->right) {  // 葉子節點
        if (*count >= *capacity) {
            *capacity *= 2;
            *result = realloc(*result, *capacity * sizeof(int));
        }
        (*result)[(*count)++] = depth;
        return;
    }
    
    leafDepthsRec(root->left, depth + 1, result, count, capacity);
    leafDepthsRec(root->right, depth + 1, result, count, capacity);
}

int* getLeafDepths(TreeNode *root, int *returnSize) {
    int *result = malloc(16 * sizeof(int));
    int count = 0, capacity = 16;
    leafDepthsRec(root, 0, &result, &count, &capacity);
    *returnSize = count;
    return result;
}

迭代實現（顯式棧，避免棧溢出）

typedef struct StackNode {
    TreeNode *node;
    int depth;
    struct StackNode *next;
} StackNode;

void push(StackNode **top, TreeNode *node, int depth) {
    StackNode *sn = malloc(sizeof(StackNode));
    sn->node = node; sn->depth = depth; sn->next = *top; *top = sn;
}

int pop(StackNode **top, TreeNode **node, int *depth) {
    if (!*top) return 0;
    StackNode *sn = *top;
    *node = sn->node; *depth = sn->depth;
    *top = sn->next;
    free(sn);
    return 1;
}

int* getLeafDepthsIter(TreeNode *root, int *returnSize) {
    int *result = malloc(16 * sizeof(int));
    int count = 0, capacity = 16;
    StackNode *stack = NULL;
    
    if (root) push(&stack, root, 0);
    
    TreeNode *node; int depth;
    while (pop(&stack, &node, &depth)) {
        if (!node->left && !node->right) {
            if (count >= capacity) {
                capacity *= 2;
                result = realloc(result, capacity * sizeof(int));
            }
            result[count++] = depth;
        }
        if (node->right) push(&stack, node->right, depth + 1);
        if (node->left) push(&stack, node->left, depth + 1);
    }
    
    *returnSize = count;
    return result;
}

層序遍歷（BFS，自然獲得深度）

typedef struct QueueNode {
    TreeNode *node;
    int depth;
    struct QueueNode *next;
} QueueNode;

int* getLeafDepthsBFS(TreeNode *root, int *returnSize) {
    int *result = malloc(16 * sizeof(int));
    int count = 0, capacity = 16;
    
    QueueNode *head = NULL, *tail = NULL;
    if (root) {
        head = tail = malloc(sizeof(QueueNode));
        head->node = root; head->depth = 0; head->next = NULL;
    }
    
    while (head) {
        TreeNode *node = head->node;
        int depth = head->depth;
        QueueNode *tmp = head;
        head = head->next;
        if (!head) tail = NULL;
        free(tmp);
        
        if (!node->left && !node->right) {
            if (count >= capacity) {
                capacity *= 2;
                result = realloc(result, capacity * sizeof(int));
            }
            result[count++] = depth;
        }
        if (node->left) {
            QueueNode *qn = malloc(sizeof(QueueNode));
            qn->node = node->left; qn->depth = depth + 1; qn->next = NULL;
            if (tail) tail->next = qn; else head = qn;
            tail = qn;
        }
        if (node->right) {
            QueueNode *qn = malloc(sizeof(QueueNode));
            qn->node = node->right; qn->depth = depth + 1; qn->next = NULL;
            if (tail) tail->next = qn; else head = qn;
            tail = qn;
        }
    }
    
    *returnSize = count;
    return result;
}

複雜度對比

BST 特有優化

利用 BST 有序性質，可在構建時記錄深度，查詢時 O(1) 獲取：

typedef struct BSTNode {
    int val, depth;
    struct BSTNode *left, *right;
} BSTNode;

BSTNode* insert(BSTNode *root, int val, int depth) {
    if (!root) {
        BSTNode *n = malloc(sizeof(BSTNode));
        n->val = val; n->depth = depth; n->left = n->right = NULL;
        return n;
    }
    if (val < root->val) root->left = insert(root->left, val, depth + 1);
    else if (val > root->val) root->right = insert(root->right, val, depth + 1);
    return root;
}

// 查詢葉子深度：遍歷時直接讀取 node->depth

測試驗證

TreeNode* createNode(int val) {
    TreeNode *n = malloc(sizeof(TreeNode));
    n->val = val; n->left = n->right = NULL;
    return n;
}

int main() {
    //      5
    //     / \
    //    3   8
    //   / \   \
    //  2   4   9
    //         /
    //        7
    TreeNode *root = createNode(5);
    root->left = createNode(3);
    root->right = createNode(8);
    root->left->left = createNode(2);
    root->left->right = createNode(4);
    root->right->right = createNode(9);
    root->right->right->left = createNode(7);
    
    int size;
    int *depths = getLeafDepthsBFS(root, &size);
    printf("葉子節點深度: ");
    for (int i = 0; i < size; i++) printf("%d ", depths[i]);
    // 預期輸出: 2 2 3  (節點 2,4,7)
    free(depths);
    return 0;
}

工程建議

• 生產環境優先迭代 DFS：空間可控、無棧溢出風險
• 需按深度分組統計時用BFS
• 頻繁查詢葉子深度考慮節點存儲深度
• 大規模樹（>10⁶ 節點）考慮內存池分配節點

掌握三種遍歷模式，能靈活應對樹相關的各類深度、路徑、層級問題。