LeetCode 894: All Possible Full Binary Trees

Question

I'm posting my code for a LeetCode problem copied here. If you would like to review, please do so. Thank you for your time!

Problem

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

Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

Example 1:

Input: 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]
        ]

Note:

1 <= N <= 20

Code

#include <vector>

class Solution {
public:
    static TreeNode *clone_tree(const TreeNode *node) {
        TreeNode *root = new TreeNode(0);
        root->left = (node->left) ? clone_tree(node->left) : nullptr;
        root->right = (node->right) ? clone_tree(node->right) : nullptr;
        return root;
    }

    static std::vector<TreeNode *> allPossibleFBT(const size_t n) {
        std::vector<TreeNode *> full_binary_trees;

        if (n == 1) {
            // full_binary_trees.push_back(new TreeNode(0));
            full_binary_trees.emplace_back(new TreeNode(0));

        } else if (n & 1) {
            for (size_t index = 2; index <= n; index += 2) {
                const auto left = allPossibleFBT(index - 1);
                const auto right = allPossibleFBT(n - index);

                for (size_t left_index = 0; left_index < left.size(); left_index++) {
                    for (size_t right_index = 0; right_index < right.size(); right_index++) {
                        full_binary_trees.emplace_back(new TreeNode(0));

                        if (right_index == right.size() - 1) {
                            full_binary_trees.back()->left = left[left_index];
                        } else {
                            full_binary_trees.back()->left = clone_tree(left[left_index]);
                        }

                        if (left_index == left.size() - 1) {
                            full_binary_trees.back()->right = right[right_index];
                        } else {
                            full_binary_trees.back()->right = clone_tree(right[right_index]);
                        }
                    }
                }
            }

        }

        return full_binary_trees;
    }
};

• Problem

• Solution

• Discuss

Answer 1

Make clone_tree() private

Make helper functions that are not part of the public API private.

Avoid unnecessary nesting of statements if possible

In allPossibleFBT() there's a lot of indentation. There's a risk of the code running off the right hand side of the screen, making it hard to read. Try to reduce nesting if possible (but only if it improves readability and maintainability). In this case, you can get rid of the outermost if-statements by doing an early return if n is even, and then unconditionally adding the single-node tree:

static std::vector<TreeNode *> allPossibleFBT(const size_t n) {
    // Exit early if n is even
    if ((n & 1) == 0)
        return {};

    // Start with the one-node tree
    std::vector<TreeNode *> full_binary_trees{new TreeNode(0)};

    // Add more complex trees
    for (size_t index = 2; ...) {
        ...
    }

    return full_binary_trees;
}

Take a reference of an object if you are using it a lot

When we see a common expression being reused a lot, we can create a new variable holding the result of that expression. When the expression is actually an object, and we don't want to copy the object, we can still avoid repeating the expression by creating a reference to that object. So instead of explicitly writing full_binary_trees.back() many times, write:

auto &root = full_binary_trees.emplace_back(new TreeNode(0));

if (right_index == right_size() - 1) {
    root->left = ...

Since C++17, emplace_back() returns a reference to the emplaced element. In case you are writing code for older standards, you could write:

full_binary_trees.emplace_back(new TreeNode(0));
auto &root = full_binary_trees.back();
...

But perhaps it would even be better to first created the new tree, and then append it to the vector at the end:

auto root = new TreeNode(0);

if ...

full_binary_trees.emplace_back(root);

Other possible improvements

It would be nice to get rid of the inner-most if-statements, which is possible if you don't care about memory leaks:

for (auto left: allPossibleFBT(index - 1)) {
    for (auto right: allPossibleFBT(n - index)) {
        auto root = new TreeNode(0);
        root->left = clone_tree(left);
        root->right = clone_tree(right);
        full_binary_trees.emplace_back(root);
    }
}

In the context of this LeetCode problem, which doesn't state whether or not you are allowed to link a node into multiple trees, you might even get away with not calling clone_tree() at all, but just writing root->left = left; root->right = right.

Also note that this problem might benefit from memoization.