引言
二叉树的输入输出是C/C++软件工程师面试的必考部分，其常考内容有前序遍历、中序遍历和后续遍历一个集中输入输出计算，本节主要介绍在二叉树中如何找出指定路径的二叉树序列。
寻找二叉树的指定路径
示例：输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
1.
该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n
如二叉树root为{10,5,12,4,7},expectNumber为22
则合法路径有[[10,5,7],[10,12]]
数据范围:
树中节点总数在范围[0,]内
-=节点值=
-=expectNumber=
代码设计思路：要解决此类问题，我们可以考虑从root节点出发，找和为sum的路径，然后分别在二叉树的左节点和有节点进行查询，当和刚好为指定的数字是，则返回相应路径，如果遍历了左右节点均无法找到相关路径时，则返回失败。
而要实现该功能，最简便的思路就是使用递归法来解决——
明白递归函数的功能：getPath(TreeNode*root,intsum,vectorintpath,vectorvectorintres)，从root节点出发，找和为sum的路径
递归终止条件：当root节点为叶子节点并且sum==root-val,表示找到了一条符合条件的路径
下一次递归：如果左子树不空，递归左子树getPath(TreeNode*root,intsum,vectorintpath,vectorvectorintres),如果右子树不空，递归右子树，getPath(TreeNode*root,intsum,vectorintpath,vectorvectorintres)
测试用例如下：
示例1
输入：
{10,5,12,4,7},22
复制
返回值：
[[10,5,7],[10,12]]
复制
说明：
返回[[10,12],[10,5,7]]也是对的
示例2
输入：
{10,5,12,4,7},15
复制
返回值：
[]
复制
示例3
输入：
{2,3},0
复制
返回值：
[]
复制
示例4
输入：
{1,3,4},7
复制
返回值：
[]
首先提供一个可用的数据结构：
structTreeNode{
intval;
structTreeNode*left;
structTreeNode*right;
TreeNode(intx):
val(x),left(NULL),right(NULL)
{
}
};
获取满足条件的路径
voidgetPath(TreeNode*root,intsum,vectorintpath,vectorvectorintres)
{
path.push_back(root-val);
if(sum==root-val!root-left!root-right)//递归终止条件
{
res.push_back(path);
}
if(root-left)//左子树不为空时
getPath(root-left,sum-root-val,path,res);
if(root-right)//右子树不为空时
getPath(root-right,sum-root-val,path,res);
path.pop_back();//对代码进行回溯，代表当前path中的root节点我已经不需要了。
}
最终寻找相关符合条件的路径：
购买专栏解锁剩余15%