112. Path Sum

, ,

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        if (root.left == null && root.right == null && root.val == targetSum) {
            return true;
        }

        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

需要注意的是，题意要求路径为根节点到叶子节点的路径，如果 [1, 2] 这样一颗树，单独的 1 不能算为一条路径，因为其还有子节点 2。另一个需要注意的地方为节点的值可能为负数，所以 root.val > targetSum 这样的剪枝条件不能使用。

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> sumQueue = new LinkedList<>(); // 包含当前节点值的和
        nodeQueue.add(root);
        sumQueue.add(root.val);

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            int sum = sumQueue.poll();
            if (node.left == null && node.right == null && sum == targetSum) {
                return true;
            }

            if (node.left != null) {
                nodeQueue.add(node.left);
                sumQueue.add(sum + node.left.val);
            }
            if (node.right != null) {
                nodeQueue.add(node.right);
                sumQueue.add(sum + node.right.val);
            }
        }

        return false;
    }
}

References

112. Path Sum