牛客网剑指offer第24题——二叉树中和为某一值的路径

题目：输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前）

这个题目的思路如下：

举例：

二叉树中有两条和为22的路径：{10,5,7}和{10,12}

2.思路

本题使用前序遍历的方式访问节点，使用二维向量result存储全部路径，使用一维向量tmp存储当前路径。遍历二叉树的过程：按前序遍历顺序访问每一个节点。访问每个结点时，将结点添加到路径向量tmp中。如果当前结点是叶子结点，则判断当前路径是否是符合条件的路径，符合条件的路径存入到二维向量result；如果当前结点不是叶子结点，则递归当前节点的左右子节点。举例：

思路分析：按照我上一篇讲的，严格按照3步走策略：

第一步:寻找子结构的输入参数的表达式

因为我们知道要用递归，那么这个问题的子结构的输入参数表达式如下：

1             FindPath(root->left,expectNumber-root->val);//假设最后一步，这里都不满足
2             FindPath(root->right,expectNumber-root->val);//假设最后一步，这里也不满足

也就是说，我们寻找当前树的左右子节点，以及给定值减去当前值作为子结构的输入参数

第二步，寻找递归结构

这个题目显然要我们寻找符合条件的路径，因此，我们自然要去遍历，因此子结构即为无脑遍历当前节点的左右子树即可，即上述代码：

第三步，边界条件

什么时候才算找到了了呢？也就是当前节点为叶子节点，且叶子节点的数值等于给定数值，即：

1         if(root->val == expectNumber && root->left == nullptr && root->right == nullptr)
2         {
3             sum_equal.push_back(tmp);
4         }

完了吗？没完，为何？

因为，我们要做的是遍历，tmp存取了我们访问路径上的所有的值，假如当前路径一直到叶子节点都不满足时。此时我们要做的就是从叶子节点退回到上一步。这就意味着当前叶子节点的值应该从tmp中删除。

我们再来回顾：

1             FindPath(root->left,expectNumber-root->val);//假设最后一步，这里都不满足
2             FindPath(root->right,expectNumber-root->val);//假设最后一步，这里也不满足

这两行代码，问：什么时候，彻底执行完毕？

答：当root已经是叶子节点的时候，此时就执行完毕了。执行完毕后。无论当前路径是否符合条件的路径，都要退回到上一步重新遍历，因此我们需要对tmp做出栈（暂时这么叫）。

即有：

1            if(tmp.size() != 0)//因为最后一步不满足，所以，这里应该把存入的元素取出来
2               tmp.pop_back();

完整代码如下：

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     vector<int> tmp;
13     vector<vector<int> > sum_equal;//这两个变量要定义在外面
14     vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
15         if(root == nullptr)
16             return sum_equal;//边界处理
17         tmp.push_back(root->val);
18         if(root->val == expectNumber && root->left == nullptr && root->right == nullptr)
19         {
20             sum_equal.push_back(tmp);
21         }
22         //if(root->val == expectNumber && root->left != nullptr || root->right != nullptr)
23          //   return;//降低程序执行时间？这样的做法不对，因为可能下面会产生抵消
24             FindPath(root->left,expectNumber-root->val);//假设最后一步，这里都不满足
25             FindPath(root->right,expectNumber-root->val);//假设最后一步，这里也不满足
26            if(tmp.size() != 0)//因为要遍历所有路径，所以，这里应该把存入的元素取出来
27               tmp.pop_back();
28         return sum_equal;
29     }
30 };

这个题目的关键难点在于你是否认识到：这棵树只是一颗普通的树，需要我们遍历所有的节点到叶子节点。

还有一个问题是：16行和28行的 return sum_equal；只有在根节点处的返回才具有意义，其他地方的返回只是为了保证和返回类型一致，并无实际意义，因为tmp和sum_equal本质是一个全局变量。

这道题最难的代码就是26-27行的代码，我们应该思考这样做的意义，以及，它为何只能存在于这个位置！

所以这道题的核心仍然是：这棵树只是一棵普通的树，需要我们遍历所有的节点到叶子节点。

再次对递归做出总结：

第一步：将递归调用假想成一般的函数调用（克服害怕心里）

第二步：找子结构输入参数的表达式

第三步：找子结构本身的表达式

第四步：对于边界条件的思考