java - leetcode 437题为什么子节点也应用DFS？

Question

我正在研究Leetcode问题437 Path Sum III，并在java上使用DFS解决它:

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static int pathSum(TreeNode root, int sum) {
        return dfs(root, sum)+pathSum(root.left, sum)+pathSum(root.right, sum);
    }

    public static int dfs(TreeNode root, int sum) {
        if (root == null) return 0;
        int count = 0;
        if (root.val == sum) count++;

        count += dfs(root.left, sum - root.val);
        count += dfs(root.right, sum - root.val);

        return count;
    }

在pathSum()方法的返回语句中，为什么我们需要“dfs(root, sum)+dfs(root.left, sum)+dfs(root.right, sum)”，而不是简单的“dfs(root, sum)” sum)(这个返回错误答案)”？有人解释说这是因为“路径不需要在根或叶子处开始或结束”(来自 lc437)。如果是这样，那么为什么我们只需要检查root的 child ，而不是root的 child 的 child ？

Answer 1

为了避免 NullPointerException，您需要对 pathSum 进行一些小更改:

public static int pathSum(TreeNode root, int sum) {
    if( root == null) return 0;
    return dfs(root, sum)+pathSum(root.left, sum)+pathSum(root.right, sum);
}

考虑给定的树:

现在让我们从根节点开始遍历树，寻找长度为 8 的路径。这可以通过从 pathSum 中省略 +pathSum(root.left, sum)+pathSum(root.right, sum); 来实现:

public static int pathSum(TreeNode root, int sum) {
    if( root == null) return 0;
    //check root only 
    return dfs(root, sum);//+pathSum(root.left, sum)+pathSum(root.right, sum);
}

返回 0，因为没有从根开始、长度为 0 的路径。
所以现在我们要检查子树。是否存在从 root.right 开始的长度为 8 的路径？我们可以这样做:

public static int pathSum(TreeNode root, int sum) {
    if( root == null) return 0;
    //check root, check root.right and return the sum 
    return dfs(root, sum) + pathSum(root.right, sum) ;//+pathSum(root.left, sum);
}

这应该返回 1，因为有一条路径从 root.right 开始，长度为 8:-3 -> 11
我希望这能澄清为什么我们需要检查根以及左右以获得完整的结果。

<小时/>旁注:通过以非递归方式检查所有树节点可以获得相同的结果。例如:

    Stack<TreeNode> stack = new Stack<>();
    stack.add(root);
    int count = 0;
    while (! stack.isEmpty()){
        TreeNode node = stack.pop();
        count += dfs(node,8);
        if(node != null) {
            stack.add(node.left);
            stack.add(node.right);
        }
    }
    System.out.println(count);