leetcode 112. Path Sum

Seawolf

1. 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.
   
2. 
   
3. Note: A leaf is a node with no children.
   
4. 
   
5. Example:
   
6. 
   
7. Given the below binary tree and sum = 22,
   
8. 
   
9.       5
   
10.      / \
    
11.     4   8
    
12.    /    / \
    
13. 11  13  4
    
14. /  \    \
    
15. 7   2    1
    
16. 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. class Solution {
    
11.    
    
12.     public boolean hasPathSum(TreeNode root, int sum) {
    
13.         
    
14.         if( root == null ) return false;
    
15.         
    
16.         sum = sum - root.val;
    
17.         
    
18.         if(root.left == null && root.right == null && sum == 0) return true;
    
19.         
    
20.         return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    
21.         
    
22.     }
    
23.    
    
24. }

复制代码