Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 15

Description

Check Completeness of a Binary Tree

Given the root of a binary tree, determine if it is a complete binary tree.

In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

Input: root = [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

Constraints:

• The number of nodes in the tree is in the range [1, 100].
• 1 <= Node.val <= 1000

Solution

class Solution {
  enum state{ fail, complete, full };
  const pair<state, int> FAIL{fail, -1};
  // pair(state, height)
  pair<state, int> helper(TreeNode *root) {
    if(!root) return make_pair(full, 0);
    auto [leftState, leftHeight] = helper(root->left);
    auto [rightState, rightHeight] = helper(root->right);
    
    // fail if any of left/right subtree is not a complete tree
    if(leftState == fail || rightState == fail) return FAIL;
    
    // fail if height of left subtree is less than or is two or more greater than right subtree's
    // it's fail
    if(leftHeight < rightHeight || leftHeight > rightHeight + 1) return FAIL;
    
    if(leftHeight == rightHeight) {
      // left subtree is complete but not full, and have right subtree, it's fail
      if(leftState == complete) return FAIL;
      // if left subtree is full, then state of tree is depend on right subtree
      return {rightState, leftHeight + 1};
    }
    
    // height of left subtree is one greater than right subtree's
    // if right subtree is not full, it's fail
    if(rightState != full) return FAIL;
    // otherwise, it's a complete binary tree
    return {complete, leftHeight + 1};
  }
public:
  bool isCompleteTree(TreeNode* root) {
    auto [state, height] = helper(root);
    return state != fail;
  }
};

// Accepted
// 120/120 cases passed (7 ms)
// Your runtime beats 43.82 % of cpp submissions
// Your memory usage beats 78.75 % of cpp submissions (10.4 MB)