[LeetCode] Path Sum II

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

For 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]
]

Solution:
注意树为空的情况，同时注意val可以为负，所以实际上需要把所有的路径都算出来。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > ans;
    int target;
    void search(vector<int> cur, int sum, TreeNode *node)
    {
        if(node == NULL) 
            return;
        else
        {
            cur.push_back(node -> val);
            if(sum + node -> val == target && node -> left == NULL && node -> right == NULL)
            {
                ans.push_back(cur);
                return;
            }
            
            if(node -> left != NULL)
                search(cur, sum + node -> val, node -> left);
            if(node -> right != NULL)
                search(cur, sum + node -> val, node -> right);
        }
    }
    
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        target = sum;
        vector<int> cur;
        if(root == NULL) return ans;
        
        search(cur, 0, root);
        return ans;
    }
};