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 andsum = 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.
题目标签:Tree
这道题目给了我们一个二叉树和一个sum, 让我们判断这个二叉树是否有至少一条path 的之和是等于sum的。利用preOrder 来遍历树,每次用sum 减去当前点的值,每当遇到一个leaf node 的时候检查sum 是不是等于0, 返回ture 和false。利用 || 来return 所有的boolean 值, 至少有过一个true,一个path之和等于sum, 总的boolean 就是true。
Java Solution:
Runtime beats 13.93%
完成日期:07/03/2017
关键词:Tree
关键点:当是leaf node 的时候检查sum;利用 || return两个children的返回值
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution 11 {12 public boolean hasPathSum(TreeNode root, int sum) 13 {14 if(root == null)15 return false;16 17 sum -= root.val;18 19 if(root.left == null && root.right == null)20 {21 if(sum == 0)22 return true;23 else 24 return false;25 }26 27 return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);28 }29 }
参考资料:
http://www.cnblogs.com/springfor/p/3879825.html
LeetCode 算法题目列表 -