leetcode：Path Sum II （途径之和，记录结果路径）【面试算法题】

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.

              5             / \            4   8           /   / \          11  13  4         /  \    / \        7    2  5   1

return

[   [5,4,11,2],   [5,8,4,5]]

题意找到所有路径，满足从根节点到叶子节点的和等于sum，输出所有满足条件的路径。

用data记录dfs路径的每一个值，当满足条件的时候，把记录的路径存到vector中再存到结果中。

其他步奏和上一题一样。

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {private:    int data[1000];    vector<vector<int>> result;public:    vector<vector<int> > pathSum(TreeNode *root, int sum) {        result.clear();        dfs(root,sum,0);        return result;    }    void dfs(TreeNode *root,int sum,int index)    {        if(!root)return;        if(root->val==sum && root->left==NULL && root->right==NULL)        {            vector<int >t;            for(int i=0;i<index;++i)t.push_back(data[i]);            t.push_back(sum);            result.push_back(t);            return;        }        sum-=root->val;        data[index]=root->val;        if(root->left)dfs(root->left,sum,index+1);        if(root->right)dfs(root->right,sum,index+1);    }};// blog.csdn.net/havenoidea