二叉树中的dfs_二叉树dfs

上周去华为面试的时候，遇到了一个自己以前积累过的dfs问题，当时觉得dfs的问题不需要搞懂每一步到哪里了，只需要大体上知道怎么弄套模板就可以，后来现场画那个dfs的图，以及每个状态的变化，虽然画出来了，但是觉得还是要好好思考下这些问题，毕竟面试时候人家更多是考察思路，而不是某个问题的具体解，不可能把所有问题都面面俱到，但是理解了问题才是最重要的啊！

举个例子：

leetcode ：113. 路径总和 II

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22

比如这个题目，都知道要用vector<vector<int>> res来存储结果，并且用vector<int> path来保存路径，用sum来存储当前路径和，当然res必须传入引用，是为了在函数调用结束之后，把所有的路径都输出出来，如果你传的是值，那么递归出来之后仍然是{}；path可以传引用，也可以不传，如果传引用，就避免了每次调用拷贝构造函数，极大的缩小了内存开销，但是要注意，在你访问到叶子结点并且sum == target的时候，直接把path添加到res中，然后返回时候要注意，必须把path.pop_back()，因为你递归一条路径[5,4,11,2]，已经满足了条件，如果直接返回，那你下次去遍历root结点5右子树的时候，虽然你sum以值的形式传递，此时的sum编程了20，可是在你path数组中仍然是[5,4,11,2]，这就会造成错误；当然sum也是可以传引用和值，不过传引用意义不大，因为你递归的回来的时候，它自动减去这个node的val就可以了，并且它只是一个普通变量，不会带来类拷贝的那么大开销，所以传值就可以了，这一点因为看过好几个人的代码，弄的自己云里雾里的！还是要多多思考啊！这个过程！

总结：有几个关键点要理解

1.dfs传引用和传值的区别

2.递归终止的条件是什么？

3.到达满足条件之后怎么处理？