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,5]
]

解题思路:

    通过遍历树保存从根到叶子节点的路径和路径和。然后推断其和是否等于sum就可以.

解题代码:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x),left(NULL),right(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode *rt,long long sum,vector<vector<int> > &ans,vector<int> &path)
    {
        path.push_back(rt->val);
        if (rt->left == rt->right && rt->left == NULL)
        {
            if (sum == rt->val)
                ans.push_back(vector<int>(path.begin(),path.end()));
            path.erase(path.end()-1);
            return ;
        }
        if (rt->left)
            dfs(rt->left,sum - rt->val,ans,path);
        if (rt->right)
            dfs(rt->right,path);
        path.erase(path.end()-1);
    }
    vector<vector<int> > pathSum(TreeNode *root,int sum) 
    {
        vector<vector<int> > ans ;
        if (!root)
            return ans ;
        vector<int> path;
        dfs(root,sum,path);
        return ans ;
    }
};