Binary Tree Path Sum.png

解題思路 ：

Back Track 不斷把 node 的值放入 path 接著檢查累積的 value 總和 如果等於 target 則將 path 存入 result 然後進行 dfs 的 recursive call 接著 pop 掉一開始剛剛放入 path 的數值 完成 Back Track 的作業方式

C++ code :

<pre><code>
/**

• Definition of TreeNode:
• class TreeNode {
• public:

• int val;
  

• TreeNode *left, *right;
  

• TreeNode(int val) {
  

•     this->val = val;
  

•     this->left = this->right = NULL;
  

• }
  

• }
  */

class Solution {

public:

/**
 * @param root the root of binary tree
 * @param target an integer
 * @return all valid paths
 */
void helper(TreeNode *root, int target, int sum, vector<int> &path, vector<vector<int>> &res) 
{   
    if(root == nullptr) return;
    sum += root->val;
    path.emplace_back(root->val);
    if(root->left == nullptr && root->right == nullptr && sum == target) 
    {
        res.emplace_back(path);
    }
    helper(root->left, target, sum, path, res);
    helper(root->right, target, sum, path, res);
    path.pop_back();
}

vector<vector<int>> binaryTreePathSum(TreeNode *root, int target) {
    // Write your code here
    vector<vector<int>> res;
    vector<int> path;
    helper(root, target, 0, path, res);
    return res;
}

};