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

July LeetCoding Challenge 23

Description

All Possible Full Binary Trees

Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Example 1:

Input: n = 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

Example 2:

Input: n = 3
Output: [[0,0,0]]

Constraints:

• 1 <= n <= 20

Solution

class Solution {
  vector<vector<TreeNode*>> FBTs;
  void generateFBTs(int N) {
    FBTs.resize(N+1);
    FBTs[1].push_back(new TreeNode(0));
    for(int i = 3; i <= N; i += 2) {
      for(int j = 1; j < i; j += 2) {
        for(auto left : FBTs[j]) {
          for(auto right: FBTs[i-j-1]) {
            FBTs[i].push_back(new TreeNode(0, deepcopy(left), deepcopy(right)));
          }
        }
      }
    }
  }
  
  TreeNode* deepcopy(TreeNode *root) {
    if(!root) return nullptr;
    return new TreeNode(0, deepcopy(root->left), deepcopy(root->right));
  }
  
public:
  vector<TreeNode*> allPossibleFBT(int N) {
    if(N % 2 == 0) return vector<TreeNode*>();
    generateFBTs(N);
    return FBTs[N];
  }
};

// Accepted
// 20/20 cases passed (131 ms)
// Your runtime beats 19.55 % of cpp submissions
// Your memory usage beats 19.62 % of cpp submissions (37.5 MB)