Leetcode Problem 894. All Possible Full Binary Trees

894. All Possible Full Binary Trees

Leetcode Solutions

Recursion + Memoization (Top-Down DP)

  1. Check if n is odd; if not, return an empty list since full binary trees require an odd number of nodes.
  2. If n is 1, return a list containing a single node tree.
  3. If the result for n nodes is already computed, return it from the memoization map.
  4. Initialize an empty list res to store the root nodes of all possible full binary trees with n nodes.
  5. Loop over odd values of i from 1 to n - 1, and for each i, do the following: a. Recursively call the function to get all possible full binary trees with i nodes for the left subtree. b. Recursively call the function to get all possible full binary trees with n - i - 1 nodes for the right subtree. c. For each combination of left and right subtrees, create a new tree with a root node and add it to res.
  6. Store res in the memoization map with key n.
  7. Return res.
UML Thumbnail

Iterative Dynamic Programming

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...