《剑指Offer》-34-二叉树中和为某一值的路径

思路

要求是从根节点开始的路径，这会比从任意节点开始的路径简单很多

思路是从根节点开始遍历每一条路径，如果和没有达到目标值就继续向下遍历
大于就回退，等于就返回到结果集中，可以看到这是一个回溯动作

实际过程中，首先不管是等于还是大于，回退pop()操作都要执行，这样才不会影响到后面

其次，这里要求必须到叶子节点的路径，如果不是叶子节点就不算

最后这里可能出现负数，所以就不能说大于了，去掉剪枝

	vector<vector<int>> pathSum(TreeNode* root, int target) {
		vector<vector<int>> res;
		vector<int> temp;
		backTrace(root, target, res, temp);
		return res;
	}

	void backTrace(TreeNode* root, int target, vector<vector<int>>& res, vector<int>& temp) {
		if (!root) return;
		temp.push_back(root->val);
		if (root->val == target && !root->left && !root->right) res.push_back(temp);
		else {
			backTrace(root->left, target-root->val, res, temp);
			backTrace(root->right, target-root->val, res, temp);
		}
		temp.pop_back();
	}