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.
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 public boolean hasPathSum(TreeNode root, int sum) {12 boolean flag=false;13 14 if(root==null)15 return false;16 17 if(root.left==null&&root.right==null&&root.val==sum)18 {19 flag=true;20 return flag;21 }22 23 if(root.left!=null||root.right!=null)24 {25 if(root.left!=null&&flag==false)26 {27 flag=hasPathSum(root.left,sum-root.val); 28 if(flag==true)29 return flag;30 }31 32 if(root.right!=null&&flag==false)33 {34 flag=hasPathSum(root.right,sum-root.val); 35 if(flag==true)36 return flag;37 }38 39 }40 return flag;41 }42 }
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.
代码如下:
原标题:112. Path Sum
关键词: