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

思路：与  不同的是。此题须要保存全部的路径，因此，搜索完左子树的路径后应该继续搜索右子树的路径。

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector
      
       
         > pathSum(TreeNode *root, int sum) {        vector
        
         
          > result;        vector
          
            path;        pathSumHelper(result, path, root, sum);                return result;    }    private:    void pathSumHelper(vector
           
            
             > &result, vector
             
               &path, TreeNode *node, int sum) { if(node == NULL) return; if(node->left == NULL && node->right == NULL && node->val == sum) { path.push_back(node->val); result.push_back(path); path.pop_back(); return; } path.push_back(node->val); pathSumHelper(result, path, node->left, sum - node->val); pathSumHelper(result, path, node->right, sum - node->val); path.pop_back(); }};
             
            
           
          
         
        
       
      

版权声明：本文博主原创文章，博客，未经同意不得转载。