Iterative binary search solution


  • 0
    N
      class Solution {
          bool goDown(TreeNode * root, int num, int layer) {
              bitset<32> direction(num);
              for(int i = layer; i > 0; i--) {
                  if(direction[i - 1]) {
                    if(root->right) root = root->right;
                    else return false;
                  } else {
                    if(root->left) root = root->left;
                    else return false;
                  }
              }
              return root != nullptr;
          }
      public:
          int countNodes(TreeNode* root) {
              int layer = 0;
              if(!root) return 0;
              TreeNode * depthWalker = root;
              while(depthWalker->left) {
                  depthWalker = depthWalker->left;
                  layer++;
              }
              int right = (1 << layer) - 1;
              int left = 0;
              while(left < right) {
                  int mid = left + (right - left) / 2;
                  if(goDown(root, mid, layer)) left = mid + 1;
                  else right = mid - 1;
              }
              int upper_layer_count = layer ? (1 << layer) - 1 : 0;
              int res = upper_layer_count + left;
              if(goDown(root, left, layer)) res++;
              return res;
          }
      };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.