题解 | #二叉树中和为某一值的路径(二)#

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
#include <cmath>
#include <functional>
class Solution {
public:
    vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
		vector<int> path;
		vector<vector<int>> res;
		function<void(TreeNode *, int)> dfs = [&](TreeNode *root, int expectNumber) -> void {
			if (!root) {
				return;
			}
			path.push_back(root->val);
			expectNumber -= root->val;
			if (!root->left && !root->right && expectNumber == 0) {
				res.push_back(path);
			} else {
				dfs(root->left, expectNumber);
				dfs(root->right, expectNumber);
			}
			path.pop_back();
		};
		dfs(root, expectNumber);
		return res;
    }
};

思路：递归。

当且仅当到达叶子节点，且路径和为expectNumber时，才将当前路径path放入结果集合res中，否则继续递归。