c 面试题之二叉树中和为某一值的路径（图示）。输入一棵二叉树以及一个整数，打印出二叉树里面结点值的与为输入整数的所有路径。由树的根结点开始往下一直到叶节点所经过的结点形成一条路径。二叉树结点的定义如下：

struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};

实例如下，输入如下二叉树和整数22，则打印出两条路径：10、5、7和10、12。

这是一道笔试题，考查对树这种基本数据结构以及递归函数的理解。

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

以下是是参考代码实例：

void FindPath(BinaryTreeNode* pRoot, int expectedSum,
std::vector<int>& path, int& currentSum);

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->m_nValue;
path.push_back(pRoot->m_nValue);

// 如果是叶结点，并且路径上结点的和等于输入的值
// 打印出这条路径
bool isLeaf = pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL;
if (currentSum == expectedSum && isLeaf)
{
printf(“A path is found: “);
std::vector<int>::iterator iter = path.begin();
for(; iter != path.end(); ++ iter)
printf(“%d\t”, *iter);
printf(“\n”);
}

// 如果不是叶结点，则遍历它的子结点
if (pRoot->m_pLeft != NULL)
FindPath(pRoot->m_pLeft, expectedSum, path, currentSum);
if (pRoot->m_pRight != NULL)
FindPath(pRoot->m_pRight, expectedSum, path, currentSum);

// 在返回到父结点之前，在路径上删除当前结点，
// 并在currentSum中减去当前结点的值
currentSum -= pRoot->m_nValue;
path.pop_back();
}

注意事项：

1. 递归函数FindPath的参数currentSum由引用参数修改为传值参数，那倒数第二行的currentSum -= pTreeNode->m_nValue;可以去掉。这时递归每一层时保存的就是当前层次的currentSum。

2. 题目没有说到m_nValue的值一定为正，如果m_nValue的值始终为正数的话，可以在currentSum > expectedSum时，直接返回到父节点，而不必在继续遍历它的子结点，称为剪枝。

3. 参考代码中使用std::vector来实现栈结构的操作，而没有直接使用std::stack，是因为stack不便于打印路径上的所有结点。

整理自《剑指Offer》及何海涛博客