Guest User

SumOfRootToLeafBinaryNumbers

a guest
Apr 6th, 2019
20
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class SumOfRootToLeafBinaryNumbers {
  2.  
  3.     public static final int M = 1000000007;
  4.  
  5.  
  6.     public static void main(String[] args) {
  7.         SumOfRootToLeafBinaryNumbers s = new SumOfRootToLeafBinaryNumbers();
  8.         TreeNode root = new TreeNode(1);
  9.         root.left = new TreeNode(0);
  10.         root.right = new TreeNode(1);
  11.         root.left.left = new TreeNode(0);
  12.         root.left.right = new TreeNode(1);
  13.         root.right.left = new TreeNode(0);
  14.         root.right.right = new TreeNode(1);
  15.         System.out.println(s.sumRootToLeaf(root));
  16.  
  17.         TreeNode root1 = new TreeNode(1);
  18.         root1.left = new TreeNode(1);
  19.         System.out.println(s.sumRootToLeaf(root1));
  20.     }
  21.  
  22.     public int sumRootToLeaf(TreeNode root) {
  23.         return sumRootToLeaf(root, "");
  24.     }
  25.  
  26.     public int sumRootToLeaf(TreeNode root, String s) {
  27.         if (root != null) {
  28.             if (root.left == null && root.right == null) {
  29.                 return convertToDecimal(s + root.val);
  30.             }
  31.             int lSum = sumRootToLeaf(root.left, s + root.val);
  32.             int rSum = sumRootToLeaf(root.right, s + root.val);
  33.             return (lSum + rSum) % M;
  34.         }
  35.         return 0;
  36.     }
  37.  
  38.     private int convertToDecimal(String bin) {
  39.         long sum = 0;
  40.         for (int i = 0; i < bin.length(); i++) {
  41.             int bit = bin.charAt(i) - 48;
  42.             int p = bin.length() - i - 1;
  43.             if (bit == 1) {
  44.                 sum = (sum + pow(2, p)) % M;
  45.             }
  46.         }
  47.         return (int) sum;
  48.     }
  49.  
  50.     public static long pow(int a, int n) {
  51.         if (n > 0) {
  52.             long temp = pow(a, n / 2);
  53.             temp = (temp * temp) % M;
  54.             if ((n & 1) == 1) {
  55.                 temp = (temp * a) % M;
  56.             }
  57.             return temp;
  58.         }
  59.         return 1;
  60.     }
  61.  
  62.     public static class TreeNode {
  63.         int val;
  64.         TreeNode left;
  65.         TreeNode right;
  66.  
  67.         TreeNode(int x) {
  68.             val = x;
  69.         }
  70.     }
  71. }
RAW Paste Data