[LeetCode] 112. Path Sum

Posted on | In

Problem

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Explanation

  1. We can use recursion to solve this problem. In the recrsive method, we pass the root and sum as parameters. If the root is null, then we return false. If the root has not left and no right child and its value is equals to the sum, then we return true. Then, we can recursively call this method for the left subtree and right subtree.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (sum == root.val && root.left == null && root.right == null) return true;
        return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
    }
}