LeetCode-113-Path Sum II
发布时间:2020-12-14 04:26:09 所属栏目:大数据 来源:网络整理
导读:算法描述: 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
算法描述: 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? 5 / 4 8 / / 11 13 4 / / 7 2 5 1 Return: [ [5,4,11,2],[5,8,5] ] 解题思路:回溯法。注意确认边界条件。 vector<vector<int>> pathSum(TreeNode* root,int sum) { vector<vector<int>> results; vector<int> temp; backtracking(root,results,temp,sum); return results; } void backtracking(TreeNode* root,vector<vector<int>>& results,vector<int>& temp,int sum){ if(root==nullptr) return; temp.push_back(root->val); if(sum ==root->val && root->left==nullptr && root->right==nullptr){ results.push_back(temp); } backtracking(root->left,sum-root->val); backtracking(root->right,sum-root->val); temp.pop_back(); } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |