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 }