113.Path Sum II二叉树中和为某一值的路径

本文主要是介绍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]
]

注意函数的参数传递方式，按值传递还是按引用传递，以及他们对递归调用的影响。

/*** 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二叉树中和为某一值的路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！