本文主要是介绍113.Path Sum II二叉树中和为某一值的路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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]
]
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] ]
注意函数的参数传递方式,按值传递还是按引用传递,以及他们对递归调用的影响。
/*** 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<vector<int> > pathSum(TreeNode *root, int sum) {vector<vector<int> > ret;int curSum = 0;vector<TreeNode *> path;pathSum(root,sum,curSum,path,ret);return ret;}void pathSum(TreeNode *root, int sum,int & curSum,vector<TreeNode *> &s,vector<vector<int> > &ret){if(root == 0)return;curSum += root -> val;s.push_back(root);bool isLeaf = !root->left && !root->right;if(curSum == sum && isLeaf){vector<int> tmp;vector<TreeNode *>::iterator it = s.begin();for(;it != s.end();it++)tmp.push_back((*it) -> val);ret.push_back(tmp);}if(root -> left)pathSum(root -> left,sum,curSum,s,ret);if(root -> right)pathSum(root -> right,sum,curSum,s,ret);curSum -= root -> val;s.pop_back();}};
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {vector<vector<int>> ret;if(!root)return ret;vector<int> curPath;FindPathCore(root,expectNumber,0,curPath,ret);return ret;}void FindPathCore(TreeNode *root,int expectNumber,int curSum,vector<int> &curPath,vector<vector<int>> &ret){curSum+=root->val;curPath.push_back(root->val);bool isLeaf = (!root->left && !root->right);if(curSum == expectNumber && isLeaf){ret.push_back(curPath);}if(root->left)FindPathCore(root->left,expectNumber,curSum,curPath,ret);if(root->right)FindPathCore(root->right,expectNumber,curSum,curPath,ret);curPath.pop_back();}
这篇关于113.Path Sum II二叉树中和为某一值的路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!