manthanthakker40

Path sum exists? BST

Jan 17th, 2017
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 0.95 KB | None | 0 0
  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. For example:
  4. Given the below binary tree and sum = 22,
  5. */
  6.  
  7. /**
  8.  * Definition for a binary tree node.
  9.  * public class TreeNode {
  10.  *     int val;
  11.  *     TreeNode left;
  12.  *     TreeNode right;
  13.  *     TreeNode(int x) { val = x; }
  14.  * }
  15.  */
  16. public class Solution {
  17.     public boolean hasPathSum(TreeNode root, int sum) {
  18.         if(root!=null)
  19.         return inorder(root,sum,0);
  20.         return false;
  21.     }
  22.     public static boolean inorder (TreeNode root,int sum,int current_sum)
  23.     {
  24.         if(root!=null)
  25.         {
  26.             if(root.left==null&&root.right==null&&sum==(current_sum+root.val))
  27.             return true;
  28.            
  29.             return inorder(root.left,sum,(current_sum+root.val))||inorder(root.right,sum,current_sum+root.val);
  30.         }
  31.         return false;
  32.     }
  33. }
Advertisement
Add Comment
Please, Sign In to add comment