Path Sum @LeetCode

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.

For example:
Given the below binary tree and sum = 22,

              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.

	package leetcode.combinations;
	/**
	* Solution: Divide & Conquer, same as PathSum II, if sum == 0, return retur, other false.
	* Take care: Although return false in if() doesn't matter, if it's not written, still write, but low inefficiency,
	* need to write it.
	*
	* I am not sure if this is strict Divide & Conquer, because it's not a sub tree problem, just one-way, the main var is sum
	*
	* @author jeffwan
	* @date Feb 15, 2014
	*/
	public class HasPathSum {
	public boolean hasPathSum(TreeNode root, int sum) {
	if (root == null) {
	return false;
	}
	sum -= root.val;
	if (root.left == null && root.right == null) {
	if (sum == 0) {
	return true;
	}
	return false;
	}
	// Divide
	boolean leftResult = hasPathSum(root.left, sum);
	boolean rightResult = hasPathSum(root.right, sum);
	// Conquer
	return leftResult || rightResult;
	}
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) { this.val = x; }
	}
	}

view raw HasPathSum.java hosted with ❤ by GitHub