## Sunday, October 30, 2016

### LeetCode OJ - Path Sum II

Problem:

Analysis:

We need both the sum and the path at a leaf node to see if it is good.

Solution:

Therefore, give the sum and path to the target leaf node through recursive calls. In order to avoid copying the path during recursive calls, I used reference. A caveat is that we need to make sure the path is properly restored before the function returns.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/path-sum-ii/

#include "LEET_PATH_SUM_II.h"
#include <queue>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_PATH_SUM_II
{
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
vector<vector<int>> pathSum(TreeNode* root, int sum)
{
vector<vector<int>> result;
vector<int> path;
pathSum(root, sum, 0, path, result);
return result;
}
private:
void pathSum(TreeNode* root, int target, int sum, vector<int>& path, vector<vector<int>>& result)
{
if (root == nullptr)
{
return;
}

sum = sum + root->val;
path.push_back(root->val);
if (root->left == nullptr && root->right == nullptr && sum == target)
{
result.push_back(path);
}
this->pathSum(root->left, target, sum, path, result);
this->pathSum(root->right, target, sum, path, result);
path.pop_back();
}
};
};

using namespace _LEET_PATH_SUM_II;

int LEET_PATH_SUM_II()
{
Solution solution;
TreeNode a(5);
TreeNode b(4);
TreeNode c(8);
TreeNode d(11);
TreeNode e(13);
TreeNode f(4);
TreeNode g(7);
TreeNode h(2);
TreeNode i(5);
TreeNode j(1);
a.left = &b;
a.right = &c;
b.left = &d;
c.left = &e;
c.right = &f;
d.left = &g;
d.right = &h;
f.left = &i;
f.right = &j;
}