Path Sum (Java and Python)

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.

	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.
	Definition for a binary tree node
	# class TreeNode:
	# def __init__(self, x):
	# self.val = x
	# self.left = None
	# self.right = None
	class Solution:
	# @param root, a tree node
	# @param sum, an integer
	# @return a boolean
	def hasPathSum(self, root, sum):
	if root==None:
	return False
	if root.val==sum and root.left==None and root.right==None:
	return True
	return self.hasPathSum(root.left, sum-root.val)or self.hasPathSum(root.right, sum-root.val)

view raw PathSum.py hosted with ❤ by GitHub

	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
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public boolean hasPathSum(TreeNode root, int sum) {
	if (root==null){
	return false;
	}
	if (root.val==sum && root.left==null && root.right==null){
	return true;
	}
	return hasPathSum(root.left, sum-root.val)||hasPathSum(root.right, sum-root.val);
	}
	}

view raw PathSum.java hosted with ❤ by GitHub