Leetcode Path sum II - c++编程基础

Path Sum II

Total Accepted: 6531 Total Submissions: 24225My Submissions

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

就是递归回溯法的应用。2到3星难度。

如下程序：

vector
  
    > pathSum(TreeNode *root, int sum) 
	{
		vector
   
     > rs; vector
    
      tmp; storeSums(rs, tmp, root, sum); return rs; } void storeSums(vector
     
       > &rs, vector
      
        &tmp, TreeNode *r, int sum) { if (!r) return; tmp.push_back(r->val); storeSums(rs, tmp, r->left, sum - r->val); storeSums(rs, tmp, r->right, sum - r->val); if (!r->left && !r->right && r->val == sum) rs.push_back(tmp); tmp.pop_back(); }

下面这样写法可以说是很多递归回溯程序的标准形式了：

//2014-2-17 update
	vector
  
    > pathSum(TreeNode *root, int sum) 
	{
		vector
   
     > rs; vector
    
      tmp; path(rs, tmp, root, sum); return rs; } void path(vector
     
       > &rs, vector
      
        &tmp, TreeNode *r, int sum) { if (!r) return; if (!r->left && !r->right) { if (r->val == sum) { rs.push_back(tmp); rs.back().push_back(sum); } return; } tmp.push_back(r->val); path(rs, tmp, r->left, sum - r->val); path(rs, tmp, r->right, sum - r->val); tmp.pop_back(); }