二叉树中和为某一值的路径

题目：输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.从树的根结点开始往下一直到叶结点所经过的结点形成一条路径.

二叉树中有两条和为22的路径:一条路径经过结点10,5,7，另一条路径经过结点10,12

由于路径是从根结点出发到叶结点,也就是说路径总是以根结点为起始点,因此我们要首先遍历根结点.在树的前序、中序、后序三种遍历方式中,只有前序遍历是访问根结点的.

按照前序遍历的顺序遍历图中的二叉树,在访问结点10之后，就会访问结点5.从二叉树结点的定义可以看出,在本题的二叉树结点中没有指向父节点的指针,访问到结点5的时候,我们是不知道前面经过了那些结点的,除非我们把经过的路径上的结点保存下来.每访问到一个结点的时候,我们都把当前的结点添加到路径中去.到达结点5时,路径中包含了两个结点,它的值分别是10和5.接下来的遍历到结点4,我们把这个结点也添加到路径中去.这个时候已经到达叶结点,但路径上三个结点的值之和是19.这个和不等于输入的22,因此不是符号要求的路径。

我们接着要遍历其他的结点.在遍历下一个结点之前,先要从结点4回到结点5,再去遍历结点5和右子节点7。值得注意的是,回到结点5的时候,由于结点4已经不在前往结点7的路径上,我们需要把结点4从路径中删除.接下来访问到结点7的时候,再把该结点添加到路径中.此时路径中三个结点10,5,7之和刚好是22,是一条符合要求的路径.

我们最后要遍历的结点是12.在遍历这个结点之前,需要先经历结点5回到结点10.同样,每一次当从子结点回到父节点的时候,我们都需要在路径上删除子结点.最后从结点10到达12的时候,路径上的两个结点的值之和也是22,因此这也是一条符合条件的路径.

遍历图中二叉树的过程

分析完前面具体的例子之后,我们就找到了一些规律。当用前序遍历的方式访问某一结点时,我们把该结点添加到路径上,并累加该结点的值.如果该结点为叶结点并且路径中结点值的和刚好等于输入的整数,则当前的路径符合要求,我们把它打印出来。如果当前结点不是叶结点，则继续访问它的子结点.当访问结束后,递归函数将自动回到它的父结点。因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值,以确保返回父结点时路径刚好从根结点到父结点的路径。我们不难看出保存路径的数据结构实际上就是一个栈,因为路径要与递归调用状态一致,而递归调用的本质就是一个压栈和出栈的过程。

形成了清晰的思路之后,就可以动手写代码了。下面是参考代码：

void FindPath(BinaryTreeNode* pRoot,int expectedSum)
{
 if(pRoot==NULL)
 return;
 std::vector<int> path;
 int currentSum=0;
 FindPath(pRoot,expectedSum,path,currentSum);
 }

void FindPath
(
 BinaryTreeNode* pRoot,
 int expectedSum,
 std::vector<int>& path,
 int currentSum
 )
{
 currentSum +=pRoot->value;
 path.push_back(pRoot->value);
 //如果是叶结点,并且路径上结点的和等于输入的值，打印出这条路径
 bool isLeaf =(pRoot->lchild==NULL&&pRoot->rchild==NULL);
 if(currentSum==expectedSum&&isLeaf)
 {
  printf("A path is found:");
  std::vector<int>::iterator iter=path.begin();
  for(;iter!=path.end();++iter)
  printf("%d	",*iter);
  printf("
");
 }
 //如果不是叶结点,则遍历它的子结点
 if(pRoot->lchild!=NULL)
 FindPath(pRoot->lchild,exception,path,currentSum);
 if(pRoot->rchild!=NULL)
 FindPath(pRoot->rchild,expection,path,currentSum);

 //在返回父结点之前,在路径上删除当前结点
path.pop_back();
}