Path Sum III ใน C++: หาเส้นทางที่ผลรวมเท่ากับค่าที่กำหนด

ภาพรวมปัญหา

ให้ต้นไม้ไบนารีที่แต่ละโหนดเก็บค่าจำนวนเต็ม ต้องการหาเส้นทางทั้งหมดที่เริ่มจากราก (root) ไปยังใบ (leaf) ซึ่งผลรวมของค่าโหนดในเส้นทางเท่ากับค่าที่กำหนด (target sum)

ตัวอย่าง

ต้นไม้: [5,4,8,11,null,13,4,7,2,null,null,5,1], Target Sum = 22

เส้นทางที่พบ: [[5,4,11,2], [5,8,4,5]]

อัลกอริทึม (DFS แบบปรับเปลี่ยน)

1. ใช้ฟังก์ชัน dfs ที่รับพารามิเตอร์: โหนดราก, ผลรวมที่เหลือ, และอาร์เรย์ชั่วคราว (temp)
2. ถ้าโหนดเป็น null → คืนค่า
3. ถ้าเป็นโหนดใบ (ไม่มีลูกซ้ายและลูกขวา):
   • ถ้าผลรวมที่เหลือเท่ากับค่าโหนดปัจจุบัน → เพิ่มค่าโหนดลง temp, บันทึก temp ลงผลลัพธ์, ลบค่าสุดท้ายออกจาก temp
4. คืนค่า
5. เพิ่มค่าโหนดปัจจุบันลง temp
6. เรียก dfs สำหรับลูกซ้ายด้วย sum - root->val
7. เรียก dfs สำหรับลูกขวาด้วย sum - root->val
8. ลบค่าสุดท้ายออกจาก temp (backtrack)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int> > v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << "[";
        for(int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = right = NULL;
    }
};

void insert(TreeNode **root, int val) {
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()) {
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left) {
            if(val != NULL) temp->left = new TreeNode(val);
            else temp->left = new TreeNode(0);
            return;
        } else {
            q.push(temp->left);
        }
        if(!temp->right) {
            if(val != NULL) temp->right = new TreeNode(val);
            else temp->right = new TreeNode(0);
            return;
        } else {
            q.push(temp->right);
        }
    }
}

TreeNode *make_tree(vector<int> v) {
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i < v.size(); i++) {
        insert(&root, v[i]);
    }
    return root;
}

class Solution {
public:
    vector<vector<int>> res;
    void dfs(TreeNode* root, int sum, vector<int>& temp) {
        if(!root) return;
        if(!root->left && !root->right) {
            if(sum == root->val) {
                temp.push_back(root->val);
                res.push_back(temp);
                temp.pop_back();
            }
            return;
        }
        temp.push_back(root->val);
        dfs(root->left, sum - root->val, temp);
        dfs(root->right, sum - root->val, temp);
        temp.pop_back();
    }
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        res.clear();
        vector<int> temp;
        dfs(root, sum, temp);
        return res;
    }
};

int main() {
    Solution ob;
    vector<int> v = {5,4,8,11,NULL,13,4,7,2,NULL,NULL,NULL,NULL,5,1};
    TreeNode *root = make_tree(v);
    print_vector(ob.pathSum(root, 22));
    return 0;
}

ข้อมูลนำเข้า (Input)

[5,4,8,11,null,13,4,7,2,null,null,5,1] 22

ผลลัพธ์ (Output)

[[5, 4, 11, 2], [5, 8, 4, 5]]