anonymous No title
No License Java
2019年12月08日
Copy
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public int countNodes(TreeNode root) {
    if (root == null) {
      return 0;
    }

    int level = getLevel(root);
    int ok = 1 << (level - 1);
    int ng = 1 << level;

    // binary search between low and high
    while (ng - ok > 1) {
      int mid = (ng + ok) / 2;
      if (doesExist(root, mid)) {
        ok = mid;
      } else {
        ng = mid;
      }
    }

    return ok;
  }

  public boolean doesExist(TreeNode root, int n) {
    List<Integer> order = new ArrayList<Integer>();
    while (n > 1) {
      if (n % 2 == 0) {
        order.add(0, 0);
      } else {
        order.add(0, 1);
      }
      n /= 2;
    }
    for (int i = 0; i < order.size(); i++) {
      if (order.get(i) == 0) {
        root = root.left;
      } else {
        root = root.right;
      }
    }
    return root != null;
  }

  public int getLevel(TreeNode root) {
    int level = 0;
    while (root != null) {
      level++;
      root = root.left;
    }

    return level;
  }
    
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public int countNodes(TreeNode root) {
    if (root == null) {
      return 0;
    }

    int level = getLevel(root);
    int ok = 1 << (level - 1);
    int ng = 1 << level;

    // binary search between low and high
    while (ng - ok > 1) {
      int mid = (ng + ok) / 2;
      if (doesExist(root, mid)) {
        ok = mid;
      } else {
        ng = mid;
      }
    }

    return ok;
  }

  public boolean doesExist(TreeNode root, int n) {
    List<Integer> order = new ArrayList<Integer>();
    while (n > 1) {
      if (n % 2 == 0) {
        order.add(0, 0);
      } else {
        order.add(0, 1);
      }
      n /= 2;
    }
    for (int i = 0; i < order.size(); i++) {
      if (order.get(i) == 0) {
        root = root.left;
      } else {
        root = root.right;
      }
    }
    return root != null;
  }

  public int getLevel(TreeNode root) {
    int level = 0;
    while (root != null) {
      level++;
      root = root.left;
    }

    return level;
  }
    
}

年末年始は機械学習・深層学習を勉強しませんか?
No one still commented. Please first comment.
年末年始は機械学習・深層学習を勉強しませんか?
広告
未経験から最短でエンジニアへの転職を目指すなら