描述

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

叶子节点是指没有子节点的节点。

在线评测地址

样例 1

输入: root = {5,4,8,11,#,13,4,7,2,#,#,5,1}, sum = 22               5              /              4   8            /   /            11  13  4          /      /          7    2  5   1 输出: [[5,4,11,2],[5,8,4,5]] 解释: 两条路径之和为 22： 5 + 4 + 11 + 2 = 22 5 + 8 + 4 + 5 = 22 

样例 2

输入: root = {10,6,7,5,2,1,8,#,9}, sum = 18               10              /               6    7           /     /            5  2   1  8                          9  输出: [[10,6,2],[10,7,1]] 解释: 两条路径之和为 18： 10 + 6 + 2 = 18 10 + 7 + 1 = 18 

当访问的节点是叶子节点的时候，新建一个列表，插入到 result 中，然后返回 result 。 分别遍历左右子树的节点，然后将他们分别插入到叶子节点之前。

/**  * Definition of TreeNode:  * class TreeNode {  * public:  *     int val;  *     TreeNode *left, *right;  *     TreeNode(int val) {  *         this->val = val;  *         this->left = this->right = NULL;  *     }  * }  */  class Solution { public:     /**      * @param root: a binary tree      * @param sum: the sum      * @return: the scheme      */     vector<vector<int>> pathSum(TreeNode * root, int sum) {         // Write your code here.         vector<int> path;         vector<vector<int>> Spath;         int weight = 0;         findpath(Spath,root,sum,path,weight);         return Spath;     }     void findpath(vector<vector<int>> &Spath,TreeNode* root,int sum,vector<int> &path,int weight)     {                  if(root == NULL){             return;         }         weight = weight + root->val;         path.push_back(root->val);         if(weight == sum && root->left == NULL && root->right == NULL)         {             Spath.push_back(path);             weight = weight - root->val;             path.pop_back();             return;         }         findpath(Spath,root->left,sum,path,weight);         findpath(Spath,root->right,sum,path,weight);         path.pop_back();      } }; 

更多题解参考

大佬有話說 (0)