Binary Tree Path Sum

题目：

Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.

A valid path is from root node to any of the leaf nodes.

分析：

这个题目告诉我们一个道理，在二叉树上的dfs不需要while或者for循环，只要判断是否有child，if有就继续call函数就可以了。

解法：

class Solution {
public:
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    int getSum(vector<int> path) {
        int sum = 0;
        for (int i = 0; i < path.size(); i++) {
            sum += path[i];
        }
        return sum;
    }

    void dfs(TreeNode* root, vector<int> path, vector<vector<int> >& res, int target) {

        path.push_back(root->val);

        if (root->left == NULL && root->right == NULL) {
            if (getSum(path) == target) {
                res.push_back(path);
            }
            return;
        }

        if (root->left != NULL) {
            dfs(root->left, path, res, target);
        }
        if (root->right != NULL) {
            dfs(root->right, path, res, target);
        }
    } 

    vector<vector<int>> binaryTreePathSum(TreeNode *root, int target) {
        // Write your code here
        if (root == NULL) {
            return vector<vector<int> >();
        }
        vector<vector<int> > res;
        vector<int> path;
        dfs(root, path, res, target);
        return res;
    }
};