题目描述

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

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

题解:基于深度优先的先序遍历

该题目的二叉树是从根节点、左子树、右子树开始进行遍历的，所以可以采用先序遍历的方法

代码

void dfs(TreeNode* root, int expectNumber, vector<int>& path, vector<vector<int>>& pathrsult) {
	if (!root) return;//深度递归的出口
	//每递归一次，就将数据保存
	path.push_back(root->val);
	expectNumber -= root->val;//期望值减节点值
	if (expectNumber == 0 && !root->left && !root->right)
		pathrsult.push_back(path);
	//左子树遍历
	dfs(root, expectNumber, path, pathrsult);
	//右子树遍历
	dfs(root, expectNumber, path, pathrsult);
	//当不存在遍历不存在时候，回溯，并将path中的最上一个元素弹出
	path.pop_back();
}
vector<vector<int>> FindPath(TreeNode* root, int expectNumber) {
	//         由于本题目不是二叉树两个节点之间的比较，且DFS递归的入口就是根节点
	//         采用深度优先的算法，只有先序遍历满足题目条件
	vector<vector<int>> pathrsult;
	vector<int> path;
	//递归出口
	if (!root) return pathrsult;
	dfs(root, expectNumber, path, pathrsult);
	return pathrsult;
}