劍指Offer：二叉樹中和為特定值的路徑（九度OJ 1368）

題目描述

輸入一棵二叉樹和一個整數 k，打印出所有從根節點到葉節點、節點值之和等於 k 的路徑。路徑定義為從根節點開始往下一直到葉節點所經過的節點序列。

輸入格式

• 第一行：兩個整數 n, k（1 ≤ n ≤ 10000），n 為節點數，k 為目標路徑和
• 接下來 n 行：每行三個整數 v_i, left, right，分別表示第 i 個節點的值、左孩子編號、右孩子編號（無孩子用 -1 表示）
• 節點編號從 1 開始，編號為 1 的節點為根節點

輸出格式

每個測試用例先輸出 result:，隨後按字典序輸出所有符合條件的路徑，路徑由節點編號組成。

樣例

輸入：
5 22
10 2 3
5 4 5
12 -1 -1
4 -1 -1
7 -1 -1

輸出：
result:
A path is found: 1 2 5
A path is found: 1 3
result:

解題思路

關鍵點 1：字典序輸出要求

字典序意味著：路徑 1 2 4 應在 1 3 之前輸出。實現方法：構建樹時，讓左孩子編號小於右孩子編號，然後深度優先搜索時優先遍歷左子樹，自然滿足字典序。

關鍵點 2：路徑回溯與棧存儲

使用陣列 route[] 模擬棧，top 為棧頂指針。遞歸函數參數 k 記錄當前深度（層數），回溯時將 top 恢復為 k，避免全局變量污染。

關鍵點 3：剪枝優化

若當前路徑和已超過目標值 sum，直接返回，無需繼續遞歸。

完整代碼

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

#define MAXSIZE 10005

typedef struct TreeNode {
    int num;
    int lchild;
    int rchild;
} TreeNode;

typedef struct TreeArr {
    TreeNode arr[MAXSIZE];
} TreeArr;

int route[MAXSIZE] = {0};
int top = 0;

void traceTree(TreeArr *a, int id, int sum, int sum_tmp, int k);

int main() {
    int n, sum;
    while (scanf("%d %d", &n, &sum) != EOF) {
        TreeArr *a = (TreeArr *)malloc(sizeof(TreeArr));
        
        for (int i = 1; i <= n; i++) {
            int l, r;
            scanf("%d %d %d", &a->arr[i].num, &l, &r);
            // 確保左孩子編號較小，保證字典序
            if (l < r) {
                a->arr[i].lchild = l;
                a->arr[i].rchild = r;
            } else {
                a->arr[i].lchild = r;
                a->arr[i].rchild = l;
            }
        }
        
        printf("result:\n");
        memset(route, 0, sizeof(int) * MAXSIZE);
        top = 0;
        traceTree(a, 1, sum, 0, 1);
        free(a);
    }
    return 0;
}

void traceTree(TreeArr *a, int id, int sum, int sum_tmp, int k) {
    if (id == -1 || sum_tmp + a->arr[id].num > sum) return;
    
    int test_sum = sum_tmp + a->arr[id].num;
    route[top++] = id;
    
    // 到達葉節點且和匹配
    if (test_sum == sum && a->arr[id].lchild == -1 && a->arr[id].rchild == -1) {
        printf("A path is found:");
        for (int i = 0; i < top; i++) printf(" %d", route[i]);
        printf("\n");
    }
    
    traceTree(a, a->arr[id].lchild, sum, test_sum, k + 1);
    top = k;  // 回溯：恢復棧頂
    traceTree(a, a->arr[id].rchild, sum, test_sum, k + 1);
}

/**************************************************************
 Problem: 1368
 Result: Accepted
 Time: 40 ms
 Memory: 3296 kb
 **************************************************************/

複雜度分析

• 時間複雜度：O(n)，每個節點最多訪問一次
• 空間複雜度：O(h)，h 為樹高，遞歸棧與路徑棧空間