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 <= 20This approach uses recursion to build all possible full binary trees for a given number of nodes. Since the problem exhibits overlapping subproblems, we can optimize the solution using memoization to store the results of previously solved subproblems. This significantly reduces the number of calculations needed.
The Python function allPossibleFBT uses recursion and memoization to find all full binary trees of size N. The base case is when N is 1, where there's only one full binary tree possible, which consists of a single node. We recursively solve for every odd N, considering each odd number left as a candidate for the number of nodes in the left subtree and recursively constructing left and right subtrees. Every tree is combined with a new root node, creating a list of solutions that is cached in memo for future reference.
JavaScript
The time complexity is O(2^N) due to the recursive generation of all possible subtrees. However, memoization helps to reduce the number of redundant calculations. The space complexity is also O(2^N) due to the storage of previously computed subtrees in the memo dictionary.
This approach uses dynamic programming through an iterative method to build trees from the bottom up. We generate trees with increasingly larger numbers of nodes by combining smaller full binary trees, ensuring that each construction step builds on the last.
The C++ solution utilizes a dynamic programming array dp where each entry dp[i] holds all the full binary trees possible with i nodes. Starting from the simplest case with one node, we iteratively combine smaller trees to build larger trees while ensuring balanced distribution between left and right subtrees, thereby leveraging previously computed solutions to optimize for new tree constructions.
Java
This method maintains a time complexity of O(2^N) and a space complexity of O(2^N) due to stored references of constructed trees. While iterative, it effectively mirrors the recursive/memoized strategies through explicit storage of previous calculations.
| Approach | Complexity |
|---|---|
| Recursive Approach with Caching | The time complexity is |
| Dynamic Iterative Approach | This method maintains a time complexity of |
How to solve (almost) any binary tree coding problem • Inside code • 224,587 views views
Watch 9 more video solutions →Practice All Possible Full Binary Trees with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor