【Leetcode】Path Sum II-白红宇

【Leetcode】Path Sum II

阅读量：7070 次

发布时间：2019-06-28

本文共 1292 字，大约阅读时间需要 4 分钟。

题目：

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

解题思路：用DFS算法进行搜索，搜索到叶子节点并且路径和等于设定值时，将路径存入容器。

代码：

/** * 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
      
       
        > Path;        vector
        
          CurrPath;        build_path(Path, CurrPath, root, sum);        return Path;    }private:    void build_path(vector
         
          
           > &Path,vector
           
             &CurrPath, TreeNode *root, int sum){ if(!root)return; CurrPath.push_back(root->val); if(!root->left&&!root->right){ if(root->val==sum)Path.push_back(CurrPath); }else{ build_path(Path,CurrPath,root->left,sum-root->val); build_path(Path,CurrPath,root->right,sum-root->val); } CurrPath.pop_back(); }};