112.Path Sum

Posted on | In

Solution 1: accepted 1ms

DFS. 

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    if (sum - root.val == 0 && root.left == null && root.right == null) 
        return true;
    boolean left = false;
    boolean right = false;
    if (root.left != null) // not necessary
        left = hasPathSum(root.left, sum - root.val);
    if (root.right != null)
        right = hasPathSum(root.right, sum - root.val);
    return left || right;
}

Simplified

1
2
3
4
5
6
public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    else if (sum - root.val == 0 && root.left == null && root.right == null) 
        return true;        
    return (hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val));
}