113. 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 andsum = 22,

5/\48//\11134/\/\7251

return

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


思路：

先序遍历，获取目标序列存到结果序列中。


代码如下：

/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode(intx):val(x),left(NULL),right(NULL){}*};*/classSolution{public:vector<vector<int>>pathSum(TreeNode*root,intsum){vector<vector<int>>result;vector<TreeNode*>temp;DFS(root,result,temp,0,sum);returnresult;}voidDFS(TreeNode*root,vector<vector<int>>&result,vector<TreeNode*>&tempNodePtr,intcurTotal,intsum){if(!root)return;curTotal+=root->val;tempNodePtr.push_back(root);vector<int>tempInt;if(!root->left&&!root->right&&curTotal==sum){for(inti=0;i<tempNodePtr.size();i++){tempInt.push_back(tempNodePtr[i]->val);}result.push_back(tempInt);tempInt.clear();}vector<TreeNode*>tempNodePtrLeft(tempNodePtr);vector<TreeNode*>tempNodePtrRight(tempNodePtr);DFS(root->left,result,tempNodePtrLeft,curTotal,sum);DFS(root->right,result,tempNodePtrRight,curTotal,sum);}};


2016-08-07 13:52:07