面试题25：二叉树中和为某一值的路径

利用先序遍历访问树，将节点存储在栈中，没遍历一个节点比较currentSum和expectedSum，如果currentSum比expectedSum大就没必要走下去了。如果相等且是叶子节点就输出

利用栈存储路径，没有直接使用STL中的stack的原因是在stack中只能得到栈顶元素，而我们需要打印整个路径

注意形参用引用提高效率：

 1 #include <vector>
 2 using namespace std;
 3 
 4 struct BinaryTreeNode
 5 {
 6     int                    m_nValue;
 7     BinaryTreeNode*        m_pLeft;
 8     BinaryTreeNode*        m_pRight;
 9 };
10 
11 void FindPath(BinaryTreeNode* pRoot, int expectedSum, vector<int>& path, int& currentSum);
12 
13 void FindPath(BinaryTreeNode* pRoot, int expectedSum)
14 {
15     if (pRoot == NULL)
16         return;
17     std::vector<int> path;
18     int currentSum = 0;
19     FindPath(pRoot, expectedSum, path, currentSum);
20 }
21 
22 void FindPath(BinaryTreeNode* pRoot, int expectedSum, vector<int>& path, int& currentSum)
23 {
24     if (pRoot != NULL)
25     {
26         currentSum += pRoot->m_nValue;
27         path.push_back(pRoot->m_nValue);
28     }
29 
30     if (pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL && currentSum == expectedSum)
31     {
32         vector<int>::iterator ite = path.begin();
33         while (ite != path.end())
34         {
35             printf("%d	", *ite);
36             ite++;
37         }
38 
39         printf("
");
40     }
41 
42     if (currentSum < expectedSum)
43     {
44         if (pRoot->m_pLeft != NULL)
45             FindPath(pRoot->m_pLeft, expectedSum, path, currentSum);
46         if (pRoot->m_pRight != NULL)
47             FindPath(pRoot->m_pRight, expectedSum, path, currentSum);
48     }
49 
50     path.pop_back();
51     currentSum -= pRoot->m_nValue;
52 }

http://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

 1 class Solution {
 2 public:
 3     vector<vector<int>> res;
 4     vector<int> path;
 5     void find(TreeNode* root, int sum)
 6     {
 7         if (root == NULL)return;
 8         path.push_back(root->val);
 9         if (!root->left && !root->right && sum == root->val)
10             res.push_back(path);
11         else
12         {
13             if (root->left)
14                 find(root->left, sum - root->val);
15             if (root->right)
16                 find(root->right, sum - root->val);
17         }
18         path.pop_back();
19     }
20     vector<vector<int>> FindPath(TreeNode* root, int expectNumber) {
21         find(root, expectNumber);
22         return res;
23     }
24 };