Tổng Đường Đi III Trong C++

Giả sử chúng ta có một cây nhị phân trong đó mỗi nút chứa một khóa nguyên. Chúng ta cần tìm các đường đi có tổng bằng một giá trị cho trước. Đường đi phải bắt đầu từ gốc đến lá. Chúng ta phải tìm đường đi mà tổng các giá trị bằng giá trị mục tiêu.

Nếu cây như [5,4,8,11,null,13,4,7,2,null,null,5,1], và tổng là 22, thì kết quả sẽ là:

Các đường đi là [[5,4,11,2],[5,8,4,5]].

Các Bước Giải Quyết

• Sử dụng hàm DFS (tìm kiếm theo chiều sâu) để giải quyết vấn đề này. Hàm DFS được chỉnh sửa nhẹ, hoạt động như sau: nhận tham số là gốc, tổng, và một mảng tạm.
• Nếu gốc không tồn tại, trả về.
• Nếu con trái và con phải của gốc đều rỗng (là nút lá), thì:
  • Nếu tổng = giá trị của gốc, thì thêm giá trị gốc vào mảng tạm, thêm mảng tạm vào kết quả, và xóa phần tử cuối khỏi mảng tạm.
  Trả về.
• Thêm giá trị của gốc vào mảng tạm.
• Gọi đệ quy dfs(con trái của gốc, tổng - giá trị gốc, mảng tạm).
• Gọi đệ quy dfs(con phải của gốc, tổng - giá trị gốc, mảng tạm).
• Xóa phần tử cuối khỏi mảng tạm.

Ví Dụ

Xem triển khai sau để hiểu rõ hơn:

#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;
}

Đầu Vào

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

Đầu Ra

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