Easy short c solution which beats 100%


  • 0
    C

    This is my simple solution.

    int countNodes(struct TreeNode* root) {
      int height = -1, count, level, num_leaves;
      struct TreeNode *node, *parent;
    
      node = root;
      for (node = root; node != NULL; node = node->left)
        height++;
    
      if (height == -1) {
        return 0;
      } else if (height == 0) {
        return 1;
      } else if (height == 1) {
        if (root->right)
          return 3;
        return 2;
      }
    
      num_leaves = 1 << height;
      for (level = 0; level < height; level++) {
        count = 1;
        for (parent = root, node = root->left; node->right != NULL;
             parent = node, node = node->right) {
          count++;
        }
    
        if (count == height - level) {
          if (root->right == NULL) {
            num_leaves--;
            break;
          } else if (root->right->left == NULL) {
            if (node != root->left)
              num_leaves -= ((1 << (height - level)) / 2);
            break;
          }
    
          root = root->right;
        } else {
          num_leaves -= ((1 << (height - level)) / 2);
          if (node->left != NULL) {
            num_leaves--;
            break;
          } else if (node == root->left) {
            num_leaves -= 2;
            break;
          } else if (parent->left->right != NULL) {
            num_leaves -= 2;
            break;
          }
    
          root = root->left;
        }
      }
    
      return ((1 << height) - 1) + num_leaves;
    }
    

  • 0
    C

    Runtime: 36 ms


Log in to reply
 

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