// Author: Li Long, [email protected]

// Date: Apr 17, 2014

// Source: http://oj.leetcode.com/problems/path-sum/

// Analysis: http://blog.csdn.net/lilong_dream/article/details/22875143

// 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 PathSum {

public boolean hasPathSum(TreeNode root, int sum) {

if (root == null) {

return false;

}

if (root.left == null && root.right == null) {

return root.val == sum;

}

return hasPathSum(root.left, sum - root.val)

|| hasPathSum(root.right, sum - root.val);

}

public static void main(String[] args) {

// 5

// / \

// 4 8

// / / \

// 11 13 4

TreeNode n1 = new TreeNode(5);

TreeNode n2 = new TreeNode(4);

TreeNode n3 = new TreeNode(8);

TreeNode n4 = new TreeNode(11);

TreeNode n5 = new TreeNode(13);

TreeNode n6 = new TreeNode(4);

n1.left = n2;

n1.right = n3;

n2.left = n4;

n3.left = n5;

n3.right = n6;

PathSum slt = new PathSum();

System.out.println(slt.hasPathSum(n1, 20));

System.out.println(slt.hasPathSum(n1, 21));

}

}