最近在[這里](http://zhedahht.blog.163.com/blog/static/254111742007228357325/)看到一道面試題，看了題目和作者的解答后，感覺真是強大。
題目：輸入一個整數和一棵二元樹。從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。打印出和與輸入整數相等的所有路徑。
例如輸入整數22和如下二元樹
則打印出兩條路徑：10, 12和10, 5, 7。
二元樹結點的數據結構定義為：
~~~
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
~~~
作者的解答為：
~~~
///////////////////////////////////////////////////////////////////////
// Find paths whose sum equal to expected sum
///////////////////////////////////////////////////////////////////////
void FindPath
(
BinaryTreeNode* pTreeNode, // a node of binary tree
int expectedSum, // the expected sum
std::vector<int>& path, // a path from root to current node
int& currentSum // the sum of path
)
{
if(!pTreeNode)
return;
currentSum += pTreeNode->m_nValue;
path.push_back(pTreeNode->m_nValue);
// if the node is a leaf, and the sum is same as pre-defined,
// the path is what we want. print the path
bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);
if(currentSum == expectedSum && isLeaf)
{
std::vector<int>::iterator iter = path.begin();
for(; iter != path.end(); ++ iter)
std::cout << *iter << '\t';
std::cout << std::endl;
}
// if the node is not a leaf, goto its children
if(pTreeNode->m_pLeft)
FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
if(pTreeNode->m_pRight)
FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);
// when we finish visiting a node and return to its parent node,
// we should delete this node from the path and
// minus the node's value from the current sum
currentSum -= pTreeNode->m_nValue;
path.pop_back();
}
~~~
仔細看代碼，你會發現，這種方法遍歷了解空間樹，所有的葉子節點都會訪問到，
如果二叉樹是這樣的呢：
按照這種方法，20的兩個孩子都會訪問到，但是，這在做無用功，因為，題目要求的是從根節點到葉子節點的路徑和為22，當訪問到20的時候，路徑和已是30了（大于22），再訪問20的孩子，路徑和也會大于22，這樣就沒有必要再訪問20的孩子了。
所以，應該避免這種無效搜索，在遍歷每個節點的時候，先判斷路徑和是否大于目標值，如果大于的話，則不要遍歷該節點的孩子，并且回溯。
優化后的代碼為：
~~~
void FindPath(
BinaryTreeNode* pTreeNode, // a node of binary tree
int expectedSum, // the expected sum
std::vector<int>& path, // a path from root to current node
int& currentSum // the sum of path
)
{
if(!pTreeNode)
return;
currentSum += pTreeNode->m_nValue;
if(currentSum > expectedSum){ //判斷路徑和是否會超出目標值，超出則回溯
currentSum -= pTreeNode->m_nValue;
return;
}
path.push_back(pTreeNode->m_nValue);
// if the node is a leaf, and the sum is same as pre-defined,
// the path is what we want. print the path
bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);
if(currentSum == expectedSum && isLeaf)
{
std::vector<int>::iterator iter = path.begin();
for(; iter != path.end(); ++ iter)
std::cout << *iter << '\t';
std::cout << std::endl;
}
// if the node is not a leaf, goto its children
if(pTreeNode->m_pLeft)
FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
if(pTreeNode->m_pRight)
FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);
// when we finish visiting a node and return to its parent node,
// we should delete this node from the path and
// minus the node's value from the current sum
currentSum -= pTreeNode->m_nValue;
path.pop_back();
}
~~~
在原來的代碼里增加了如下代碼：
~~~
if(currentSum > expectedSum){ //判斷路徑和是否會超出目標值，超出則回溯
currentSum -= pTreeNode->m_nValue;
return;
}
~~~
剪去無效的子樹，避免無效搜素，提高效率。
參考：[http://zhedahht.blog.163.com/blog/static/254111742007228357325/](http://zhedahht.blog.163.com/blog/static/254111742007228357325/)
