Path Sum II @leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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]
]

» Solve this problem

这题要动态存储找到的path node，思路和permutation一样。还是要注意sol.pop_back()在完成了两个递归之后。

	/**
	* 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 build(TreeNode *root, vector<vector<int> > &res, vector<int> &sol, int sum, int s)
	{
	if(!root->left&&!root->right&&(s+root->val)==sum)
	{
	sol.push_back(root->val);
	res.push_back(sol);
	sol.pop_back();
	return;
	}
	s+=root->val;
	sol.push_back(root->val);
	if(root->left) build(root->left, res, sol, sum, s);
	if(root->right) build(root->right, res, sol, sum, s);
	sol.pop_back();
	}
	vector<vector<int> > pathSum(TreeNode *root, int sum) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<vector<int> > res;
	if(!root) return res;
	vector<int> sol;
	int s=0;
	build(root, res, sol, sum, s);
	return res;
	}
	};

view raw Path Sum II hosted with ❤ by GitHub