首页 > 代码库 > Leetcode: Path Sum
Leetcode: Path Sum
1 /** 2 * Definition for binary tree 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 int depth=getdepth(root); 13 int[] path=new int[depth]; 14 if(root==null) return false; 15 return haspath(root, path, sum, 0); 16 } 17 18 public boolean haspath(TreeNode root, int[] path, int sum, int level){ 19 if(root.left==null && root.right==null){//leaf node 20 path[level]=root.val; 21 int calsum=0; 22 for(; level>=0; level--){ 23 calsum=calsum+path[level]; 24 } 25 if(calsum == sum) return true; 26 else return false; 27 } 28 if(root.left==null && root.right!=null){ 29 path[level]=root.val; 30 return haspath(root.right, path, sum, level+1); 31 } 32 if(root.left!=null && root.right==null){ 33 path[level]=root.val; 34 return haspath(root.left, path, sum, level+1); 35 }else{ 36 path[level]=root.val; 37 return haspath(root.left, path, sum, level+1) || haspath(root.right, path, sum, level+1); 38 } 39 } 40 41 public int getdepth(TreeNode r){ 42 if(r==null) return 0; 43 return Math.max(getdepth(r.left), getdepth(r.right))+1; 44 } 45 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。