题目难度：中等

题目描述：

输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点 2.叶子节点是指没有子节点的节点 3.路径只能从父节点到子节点，不能从子节点到父节点 4.总节点数目为n

如二叉树root为{10,5,12,4,7},expectNumber为22 则合法路径有[[10,5,7],[10,12]]

数据范围: 树中节点总数在范围 [0, 5000] 内 -1000 <= 节点值 <= 1000 -1000 <= expectNumber <= 1000

示例1:

输入：{10,5,12,4,7},22 返回值：[[10,5,7],[10,12]] 说明：返回[[10,12],[10,5,7]]也是对的

思路1:DFS / BFS

DFS: 时间复杂度：O($n^{2}n^2$)，空间复杂度：O(n) (n->树的节点数) 运行时间：4ms 占用内存：640KB

class Solution {
private:
  	vector<vector<int>> res;
  	vector<int> path;
public:
  	void DFS(TreeNode* root,int expectNumber) {
      	if(!root) return;
      
      	path.push_back(root);
      	expectNumber -= root->val;
      
      	if(!root->left && !root->right && !expectNumber) res.push_back(path);
      
      	DFS(root->left, expectNumber);
      	DFS(root->right, expectNumber);
      
      	path.pop_back();
    }
  
  	vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
      	if(!root) return {};
      	DFS(root, expectNumber)
      	return res;
    }
}

BFS: 时间复杂度：O($n^{2}n^2$)，空间复杂度：O(n) (n->树的节点数) 运行时间：4ms 占用内存：548KB

#include <numeric>
class Solution {
private:
  	typedef pair<vector<int>, TreeNode*> PII;
public:
  	vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
      
      	if(!root) return {};
      	vector<vector<int>> res;
      	queue<PII> q;
      	PII p({root->val}, root);
      	q.push(p);
      
      	while (!q.empty()) {
          	auto cur = q.front();
          	q.pop();
          
          	TreeNode *node = cur->second;
          
          	if(node->left) {
              	vector<int> left = cur->first;
              	left.push_back(node->left->val);
              	q.push(make_pair(left, node->left));
            }
          
          	if(node->right) {
              	vector<int> right = cur->first;
              	right.push_back(node->right->val);
              	q.push(make_pair(right, node->right));
            }
         
          	if(!node->left && !node->right) {
              	vector<int> path = cur.first;
              	int sum = accumulate(path.begin(), path.end(), 0);
              	if(sum == expectNumber) res.push_back(path);
            }
        }
      	return res;
    }
}

😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘