Path Sum II
发布时间:2020-12-14 04:44:36 所属栏目:大数据 来源:网络整理
导读:Given a binary tree and a sum,find all root-to-leaf paths where each path‘s sum equals the given sum. Note:?A leaf is a node with no children. Example:Given the below binary tree and sum = 22 , 5 / 4 8 / / 11 13 4 / / 7 2 5 1 Return:[ [
Given a binary tree and a sum,find all root-to-leaf paths where each path‘s sum equals the given sum.
Note:?A leaf is a node with no children. 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,5] ] code struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x),left(NULL),right(NULL) {} }; class Solution { public: vector<vector<int>> pathSum(TreeNode* root,int sum) { if(!root) return {}; vector<vector<int>> res; vector<int> tmp; pathSumCore(root,sum,tmp,res); return res; } private: void pathSumCore(const TreeNode* node,int sum,vector<int> &tmp,vector<vector<int>> &res) { tmp.emplace_back(node->val); if(node->left==nullptr&&node->right==nullptr) { if(sum-node->val==0) res.emplace_back(tmp); return; } if(node->left) { pathSumCore(node->left,sum-node->val,res); tmp.pop_back(); } if(node->right) { pathSumCore(node->right,res); tmp.pop_back(); } } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |