一天一道LeetCode

本系列文章已全部上传至我的github，地址：
欢迎大家关注我的新浪微博，
欢迎转载，转载请注明出处

（一）题目

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

（二）解题

题目大意：给定一个二叉树和一个整数，求所有根节点到叶子节点上的节点值的和等于该整数的路径。

相比于上一题，，本题需要保存该路径上的所有节点的值。

解题思路还是一样，但是需要用一个vector来存储路径上的节点。

/** * Definition for a binary tree node. * 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
     
      
       > ret;//用来存放结果         if(root==NULL) return ret;         dfsTree(root,sum,0,ret,vector
       
        (0));         return ret;    }    //cur：当前路径上的节点值和    //ret：符合条件的路径的集合    //temp：当前路径上的节点集合    void dfsTree(TreeNode* root, int& sum,int cur ,vector
        
         
          >& ret,vector
          
            temp) { temp.push_back(root->val); cur += root->val; if(root->left==NULL&&root->right==NULL)//判断是叶子节点 { if(cur == sum) ret.push_back(temp);//满足条件就压入集合 return; } if(root->left!=NULL) dfsTree(root->left,sum,cur,ret,temp);//遍历左子树 if(root->right!=NULL) dfsTree(root->right,sum,cur,ret,temp);//遍历右子树 }};