ORID53 DFS pathSum

112. Path Sum 解题报告

算法

这道题算比较经典的DFS，可以说就是为了找出是否有一条路径能够加到sum这个值。DFS刚好能够解决这个问题。
我思路没什么大问题，但是有点想复杂了，我想要用一个helper（这个思路也没问题，只不过如果只是为了验证是否有这条路径，不需要helper）
看了discussion里面的答案，它的精髓部分在于在每次传递下去的时候，把sum减去了当前root的值，这样每次递归的时候，只要root.left == null && root.right == null && sum - root.val == 0 的时候，你就符合标准了。
题目要求就是从root到leaf上面有一条路径能够加到sum这个值。而我一开始是想用一个值来track该路径的sum，没想要递归的精髓应该是把问题变小，所以在每次传递下去的时候，你传的值应该是sum - root.val 而不是把一个count这种记录值。
为什么用这个算法？
经典DFS。

代码实现

有什么要注意的地方？
把判断条件想好就没问题了。

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null && sum - root.val == 0) {
            return true;
        }
        return (hasPathSum(root.left, sum - root.val)) || (hasPathSum(root.right, sum - root.val));
    }

时间空间复杂度

O(n)

哪些相关题目做过的？

目前没想到。

Path Sum II 是一个意思，只不过这次要你输出所有路径的值，也就是需要一个List<Integer> 来记录当前符合条件上路径的值。
这道题用helper就非常管用了。它们管这个叫backtracking？ 也就是记录？