894. All Possible Full Binary Trees

similar to 95(construct BST), 96

DFS+MEMO

T: O(2^n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> allPossibleFBT(int n) {
        if (n % 2 == 0) {
            return new LinkedList<>();
        }
        LinkedList<TreeNode>[] memo = new LinkedList[n+1];
        return dfs(n, memo);
    }
    private List<TreeNode> dfs(int n, LinkedList<TreeNode>[] memo) {
        LinkedList<TreeNode> list = new LinkedList<>();
        if (n == 1) {
            list.add(new TreeNode(0));
            return list; 
        }
        if (memo[n] != null) {
            return memo[n];
        }
        for (int i = 1; i < n; i+=2) {
            int j = n - i - 1;
            List<TreeNode> leftTree = dfs(i, memo);
            List<TreeNode> rightTree = dfs(j, memo);
            for (TreeNode left : leftTree) {
                for (TreeNode right : rightTree) {
                    TreeNode root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    list.add(root);
                }
            }
        }
        return memo[n] = list;
    }
}

/**
odd number of nodes -> why?
ans: root + 0 or 2 children

so for left -> use i
       right -> n - i - 1(root)

so left and right are also odd number
odd + odd + root = odd number

so we can give i start with 1 and increase by 2, so...1, 3, 5...
in another side is n - odd - 1, so also odd - odd -1 = odd

base case is 1 node

          7

        root
          /\
  can be   
  1 5    3.   3.  5 1
    /\   1 1 11
    1 3 or 3 1    

there are common subproblem
so we can have a memo[n]

T: O(2^n)
 */

DP

recursion like this:

```java
0 or 2
  root
i    n-i-1

1 3 5
5 3 1

f(7) = root + f(1) + f(5)
  or 
      root + f(3) + f(3)
  or
      root + f(5) + f(1)

 f(3) = root + f(1) + f(1)   
```

become to find dp[nodesNumber]

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> allPossibleFBT(int n) {
        if (n % 2 == 0) {
            return new LinkedList<>();
        }
        List<TreeNode>[] dp = new List[n+1];
        for (int i = 0; i <= n; i++) {
            dp[i] = new ArrayList<>();
        }
        dp[1].add(new TreeNode(0));
        for (int nodesNumber = 3; nodesNumber <= n; nodesNumber+=2) { // cal each dp case
            for (int i = 1; i < count - 1; i+=2) {
                int j = count - i - 1;
                for (TreeNode left : dp[i]) {
                    for (TreeNode right : dp[j]) {
                        TreeNode root = new TreeNode(0, left, right);
                        dp[nodesNumber].add(root);
                    }
                }
            }
        }
        return dp[n];
    }
}

/**
odd number of nodes -> why?
ans: root + 0 or 2 children

so for left -> use i
       right -> n - i - 1(root)

so left and right are also odd number
odd + odd + root = odd number

so we can give i start with 1 and increase by 2, so...1, 3, 5...
in another side is n - odd - 1, so also odd - odd -1 = odd

base case is 1 node

          7

        root
          /\
  can be   
  1 5    3.   3.  5 1
    /\   1 1 11
    1 3 or 3 1    

there are common subproblem
so we can have a memo[n]

T: O(2^n)

if use bottom up, our goal is to fill out 
dp[] 
so from dp[1], dp[3], dp[5]....dp[n]
is what we want to fill out...
 */
```