Binary Tree Path Sum.png
解題思路 ：
Back Track 不斷把 node 的值放入 path 接著檢查累積的 value 總和 如果等於 target 則將 path 存入 result 然後進行 dfs 的 recursive call 接著 pop 掉一開始剛剛放入 path 的數(shù)值 完成 Back Track 的作業(yè)方式
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;
}
};
