????? 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] ]解題思路:通過遍歷樹保存從根到葉子節點的路徑和路徑和。然后推斷其和是否等于sum就可以.解題代碼: /*** Definition for binary tree* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:void dfs(TreeNode *rt,long long sum,vector<vector<int> > &ans,vector<int> &path){path.push_back(rt->val);if (rt->left == rt->right && rt->left == NULL){if (sum == rt->val)ans.push_back(vector<int>(path.begin(),path.end()));path.erase(path.end()-1);return ;}if (rt->left)dfs(rt->left,sum - rt->val,ans,path);if (rt->right)dfs(rt->right,sum - rt->val,ans,path);path.erase(path.end()-1);}vector<vector<int> > pathSum(TreeNode *root, int sum) {vector<vector<int> > ans ;if (!root)return ans ;vector<int> path;dfs(root,sum,ans,path);return ans ;} };

?

轉載于:https://www.cnblogs.com/ldxsuanfa/p/10515912.html

總結

以上是生活随笔為你收集整理的LeetCode:Path Sum II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。