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

/*
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) {
        //keep scanning
		//when reaches the leaf and the sum equals to expect number,it means a satisfied path is found
		//insert new array.

		//when back to a non-leaf node,if there are arrays in the vector  and the number of element is less than the depth,it means its in the back path.
		//new

		//scan and push.when reaches the leaf
		//if the sum equals,push to the return vector,if not,pop it back.
		
		vector<vector<int>> ret;
		vector<int> paths;
		int sum=0;
		dfs(root,expectNumber,ret,paths,sum);

		return ret;

    }
	void dfs(TreeNode * root,int expectNumber,vector<vector<int>> & ret,vector<int> & paths,int sum){

		if(root==nullptr)
			return ;
		//visit the current node,push it and calcualte the sum
		paths.push_back(root->val);
		sum+=root->val;

		//process the end
		if(root->left==nullptr && root->right==nullptr){
			//reaches the end
	 
			if(sum==expectNumber){
				ret.push_back(paths);
			}
		}
		else{
			dfs(root->left,expectNumber,ret,paths,sum);
			dfs(root->right,expectNumber,ret,paths,sum);
		}

		//when finishing visiting a node, pop it back
		paths.pop_back();
		sum-=root->val;
		return ;
	}
};

最初思路是探底，符合再自低向上加。

这个过程可以修改为探底的中途增加，符合条件算进返回结果。否则弹出。这样的优点是，返回的时候结果可以复用。

否则由于先访问叶子再返回根的特点，会引入很多空vector，回加。不如在到达叶子结点时就push ret

因为需要处理在返回途中进入另一个不符合expect number的分支。设计层级计数器难以操作。