/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: vector<vector<int>> FindPath(TreeNode* root, int expectNumber) { result.clear(); path.clear(); if (root == nullptr) return result; path.push_back(root->val); traversal(root, expectNumber - root->val); return result; } void traversal(TreeNode* cur, int count) { // 叶子节点且找到了和为sum的路径 if (cur->left == nullptr && cur->right == nullptr && count == 0) { result.push_back(path); return; } if (cur->left == nullptr && cur->right == nullptr && count != 0) { return; } if (cur->left) { path.push_back(cur->left->val); count -= cur->left->val; traversal(cur->left, count); count += cur->left->val; path.pop_back(); } if (cur->right) { path.push_back(cur->right->val); count -= cur->right->val; traversal(cur->right, count); count += cur->right->val; path.pop_back(); } return; } private: vector<int> path; vector<vector<int>> result; };