劍指 Offer Q25：二叉樹中和為給定值的路徑（前序遍歷+回溯）

問題

輸入二叉樹根節點與整數 target，打印所有從根到葉子節點路徑上節點值之和等於 target 的路徑。

算法：前序遍歷 + 路徑記錄

• 遞歸參數：當前節點、目標和、當前路徑和、路徑容器（`vector`）。
• 進入節點：累加值，加入路徑。
• 若為葉子節點且和等於目標 → 輸出路徑。
• 遞歸左右子樹。
• 回溯：彈出路徑末尾節點（恢復狀態）。

代碼實現

struct BinaryTreeNode {
    int val;
    BinaryTreeNode *left, *right;
};

vector path;

void FindPath(BinaryTreeNode* root, int target, int curSum) {
    if (!root) return;
    curSum += root->val;
    path.push_back(root);
    if (curSum == target && !root->left && !root->right) {
        for (auto node : path) printf("%d ", node->val);
        printf("\n");
    }
    FindPath(root->left, target, curSum);
    FindPath(root->right, target, curSum);
    path.pop_back(); // 回溯關鍵
}

關鍵點

• 路徑定義：必須從根到葉子（非任意節點間）。
• 回溯：`path.pop_back()` 保譯路徑容器在遞歸返回時狀態正確。
• 時間 O(n)，空間 O(h)（遞歸棧 + 路徑容器）。