[每日一题]113. Path Sum II

每日一题是一个每天刷leetcode群。x0a建群的目的在于每天讨论题目的解法，互相鼓励，提升水平。 x0a我们希望能从不同的角度去思考一个题目，举一反三！x0a通过做题提升算法水平。x0a一般是早上发题，晚上八点后讨论解法，贴代码。...





今天的题目其实跟昨天的题目的思路差不多。我总结了一下，有三种解法

1. 深度优先搜索
2. 递归
3. 使用栈(stack + while)

深度优先搜索

深度优先搜索的思路很明确，就是从root 到left 遍历树，并且记下他的路径（使用path存储），到叶节点的时候，比较路径之和 和 sum(目标数）是否相等。具体代码如下：



上面的代码是ruby，无限接近伪代码，不会ruby的同学不要在意语法，知道意思就行。

使用dfs需要注意的是

1. 在dfs方法返回前，需要将path中的最后一个元素弹出
2. 应该在叶节点在判断是否记录结果

该版本的ruby代码只击败了65%的提交，通过思考发现，每次递归的时候，我都计算了一次sum_of 。我想了一个办法，在最后不需要计算sum的值，而是每次都减去val, 这样最后只要判断sum 是否等于0. 具体看代码。



上面的代码居然打败了 100% 的Ruby提交~  值得截图庆祝！



说明一个道理，我们在做完一道题目以后，一定要记得想想优化。一次简单的优化，说不定会带来极大的性能提升。

递归

本质上说，dfs也是递归，他们代码上也长的差不多。我以前一直认为是一个事情。今天写的时候，体会完全不一样。我发现递归跟dfs有一个非常大的不同是：递归不需要考虑path的增减问题。这是一个很关键的变化！因为递归的每一层，其实是不保存状态的！每一层的递归，程序的上下文都是全局状态。具体请看代码



在代码的28行，我将当前节点的val压入path以后，在30， 31行调用递归代码，我将数据clone了一份，这样的结果是下一层的path是完全不同的对象，我不需要再递归方法结束之后弹出最后一个值。

栈

一般情况下，能写成递归的程序都能写成循环：stack+ while 或者 foreach 。



不知道为什么，这段代码的性能反而比递归的代码性能差。有兴趣的伙伴可以参考着优化一下。

如下是@Kee 的swift 版本



@欣 的C++版本



@M.renard 的Java版本



@Armey郑兆奇 提供了一个Java的stack + while 版本。 我写了半天也没有写出来（原谅我的Java渣渣）。



具体代码就不解释了~

谢谢阅读

每日一题是一个每天刷leetcode群。

建群的目的在于每天讨论题目的解法，互相鼓励，提升水平。

我们希望能从不同的角度去思考一个题目，举一反三！

通过做题提升算法水平。

一般是早上发题，晚上八点后讨论解法，贴代码。

想刷题肉身翻墙的朋友加我微信进群 ！

获取我微信号的办法

关注公众号，输入：我要刷题

    关注 一个技术人员的胡言乱语