Sponsored
Sponsored
This 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 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.
1from typing import List
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9memo = {}
10
11def allPossibleFBT(N: int) -> List[TreeNode]:
12 if N % 2 == 0:
13 return []
14 if N == 1:
15 return [TreeNode(0)]
16 if N in memo:
17 return memo[N]
18
19 result = []
20 for left in range(1, N, 2):
21 for left_subtree in allPossibleFBT(left):
22 for right_subtree in allPossibleFBT(N - 1 - left):
23 root = TreeNode(0)
24 root.left = left_subtree
25 root.right = right_subtree
26 result.append(root)
27
28 memo[N] = result
29 return resultThe 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.
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.
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.
1import java.util.*;
2
3
In this Java solution, an array of lists dp is used to store trees. Each tree is represented by a TreeNode with zero value. This iterative process combines smaller trees at each step to build bigger trees, ensuring that all trees have the characteristic of full binary trees, which inherently coordinates the nodes' distribution between left and right subtrees.