Give a binary tree, and a target number, find all path that the sum of nodes equal to target, the path could be start and end at any node in the tree.

Have you met this question in a real interview?

Yes

Example

Given binary tree:

    1
   / \
  2   3
 /
4

and target =6. Return :

[
  [2, 4],
  [2, 1, 3],
  [3, 1, 2],
  [4, 2]
]

/**
 * Definition of ParentTreeNode:
 * class ParentTreeNode {
 * public:
 *     int val;
 *     ParentTreeNode *parent, *left, *right;
 * }
 */
class Solution {
public:
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    vector<vector<int>> binaryTreePathSum3(ParentTreeNode *root, int target) {
        // Write your code here
        vector<vector<int>> res;
        dfs(root, target, res);
        return res;
    }

    void dfs(ParentTreeNode* root, int target, vector<vector<int>> &res) {
        if (root == nullptr)
            return;
        vector<int> buf;
        findSum(root, nullptr, target, buf, res);
        dfs(root->left, target, res);
        dfs(root->right, target, res);
    }

    void findSum(ParentTreeNode* root, ParentTreeNode* father, int target, vector<int> &buf, vector<vector<int>> &res) {
        target -= root->val;
        buf.push_back(root->val);
        if (target == 0)
            res.push_back(buf);

        if (root->parent != nullptr && root->parent != father)
            findSum(root->parent, root, target, buf, res);

        if (root->left != nullptr && root->left != father)
            findSum(root->left, root, target, buf, res);

        if (root->right != nullptr && root->right != father)
            findSum(root->right, root, target, buf, res);

        buf.pop_back();
    }
};