LeetCode-Path Sum

##题目

####Path Sum

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.

##解题思路
这道题是树操作的题目，判断是否从根到叶子的路径和跟给定sum相同的。还是用常规的递归方法来做，递归条件是看左子树或者右子树有没有满足条件的路径，也就是子树路径和等于当前sum减去当前节点的值。结束条件是如果当前节点是空的，则返回false，如果是叶子，那么如果剩余的sum等于当前叶子的值，则找到满足条件的路径，返回true。

##算法代码
代码采用JAVA实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * 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;
	    //已到叶子节点，且满足根结点的值等于sum
	    if(root.left==null && root.right==null && root.val==sum)
	    	return true;
	    //判断左右子树是否有满足sum-root.val值的情况。
	    return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);
	}
}