LeetCode 113. Path Sum II [Medium] [C++] 解題筆記

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

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

想法:

    這題跟112. Path Sum 是一樣的，只是需要多儲存每個找到的解，因此在遍歷的過程中需要用到一個 vector 來

儲存當前的 node。這邊有個重要的技巧是用reference的方式傳遞要儲存的path(會快非常多)，

因為dfs每次都會走訪到 leaf 再 backtrace 回來 走訪下一個路徑，所以在最後走訪結束時將該leaf從vector中pop出來

，這樣便可以重複使用同一個vector否則每多走訪一個node就要新增一條vector非常沒有效率!

完整程式碼:

class Solution {

public:

    vector<vector<int>> res;

    void traverse(TreeNode* root, int sum, vector<int>& cur) {

        if (root == nullptr) { return; }

        cur.emplace_back(root->val);

        // leaf node

        if (root->left == nullptr && root->right == nullptr && sum - root->val == 0) {

            res.emplace_back(cur);

        }

        traverse(root->left, sum - root->val, cur);

        traverse(root->right, sum - root->val, cur);

        cur.pop_back();

        return;

    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {

        vector<int> cur;

        traverse(root, sum, cur);

        return res;

    }

};