https://leetcode.com/problems/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.
1 public class Solution { 2 // private static boolean flag=false; 3 // public static boolean hasPathSum(TreeNode root, int sum) { 4 // if(root==null){return flag;} 5 //// if(root.left==null&&root.right==null&&root.val==1&&sum==0)return false; 6 // F(0,root,sum); 7 // return flag; 8 // } 9 // public static void F(int cout,TreeNode node,int sum){ 10 // if(flag==true){return;} 11 // cout+=node.val; 12 // if(node.left==null&&node.right==null&&cout==sum){flag=true;return;} 13 // if(node.left!=null){F(cout,node.left,sum);} 14 // if(node.right!=null){F(cout,node.right,sum);} 15 // } 16 public static boolean hasPathSum(TreeNode root, int sum) { 17 if (root == null) 18 return false; 19 20 if (root.left == null && root.right == null) 21 return sum == root.val; 22 23 return hasPathSum(root.left, sum - root.val) 24 || hasPathSum(root.right, sum - root.val); 25 } 26 public static class TreeNode { 27 int val; 28 TreeNode left; 29 TreeNode right; 30 31 TreeNode(int x) { 32 val = x; 33 } 34 } 35 public static void main(String[]args){ 36 TreeNode[] node=new TreeNode[5]; 37 for(int i=0;i<node.length;i++){ 38 node[i]=new TreeNode(i); 39 } 40 TreeNode node1=new TreeNode(1); 41 TreeNode node2=new TreeNode(2); 42 // node1.left=node2; 43 node[0].left=node[1]; 44 node[0].right=node[2]; 45 node[1].left=node[3]; 46 node[2].right=node[4]; 47 System.out.println(hasPathSum(node1,2)); 48 } 49 }
原文：http://www.cnblogs.com/qq1029579233/p/4478091.html