Formatted question description: https://leetcode.ca/all/894.html

894. All Possible Full Binary Trees (Medium)

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

Note:

1 <= N <= 20

Companies:
Google

Related Topics:
Tree, Recursion

Solution 1.

// OJ: https://leetcode.com/problems/all-possible-full-binary-trees/
// Time: O(2^N)
// Space: O(2^N)
class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int N) {
        if (N % 2 == 0) return {};
        if (N == 1) return { new TreeNode(0) };
        vector<TreeNode*> ans;
        for (int i = 1; i <= N - 2; i += 2) {
            auto lefts = allPossibleFBT(i);
            auto rights = allPossibleFBT(N - i - 1);
            for (auto left : lefts) {
                for (auto right : rights) {
                    auto root = new TreeNode(0);
                    root->left = left;
                    root->right = right;
                    ans.push_back(root);
                }
            }
        }
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> allPossibleFBT(int N) {
        if (N % 2 == 0)
            return new ArrayList<TreeNode>();
        Map<Integer, List<TreeNode>> map = new HashMap<Integer, List<TreeNode>>();
        List<TreeNode> oneList = new ArrayList<TreeNode>();
        oneList.add(new TreeNode(0));
        map.put(1, oneList);
        for (int i = 3; i <= N; i += 2) {
            List<TreeNode> curList = map.getOrDefault(i, new ArrayList<TreeNode>());
            int sum = i - 1;
            for (int left = 1; left < sum; left++) {
                int right = sum - left;
                List<TreeNode> leftList = map.getOrDefault(left, new ArrayList<TreeNode>());
                List<TreeNode> rightList = map.getOrDefault(right, new ArrayList<TreeNode>());
                for (TreeNode leftNode : leftList) {
                    for (TreeNode rightNode : rightList) {
                        TreeNode root = new TreeNode(0);
                        root.left = leftNode;
                        root.right = rightNode;
                        curList.add(root);
                    }
                }
            }
            map.put(i, curList);
        }
        return map.get(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 {
    private List<TreeNode>[] f = new List[21];

    public List<TreeNode> allPossibleFBT(int n) {
        return dfs(n);
    }

    private List<TreeNode> dfs(int n) {
        if (f[n] != null) {
            return f[n];
        }
        if (n == 1) {
            return Collections.singletonList(new TreeNode());
        }
        List<TreeNode> res = new ArrayList<>();
        for (int i = 0; i < n - 1; ++i) {
            int j = n - i - 1;
            for (TreeNode left : dfs(i)) {
                for (TreeNode right : dfs(j)) {
                    res.add(new TreeNode(0, left, right));
                }
            }
        }
        f[n] = res;
        return res;
    }
}

// OJ: https://leetcode.com/problems/all-possible-full-binary-trees/
// Time: O(2^N)
// Space: O(2^N)
class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int N) {
        if (N % 2 == 0) return {};
        if (N == 1) return { new TreeNode(0) };
        vector<TreeNode*> ans;
        for (int i = 1; i <= N - 2; i += 2) {
            auto lefts = allPossibleFBT(i);
            auto rights = allPossibleFBT(N - i - 1);
            for (auto left : lefts) {
                for (auto right : rights) {
                    auto root = new TreeNode(0);
                    root->left = left;
                    root->right = right;
                    ans.push_back(root);
                }
            }
        }
        return ans;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        @cache
        def dfs(n):
            if n == 1:
                return [TreeNode()]
            res = []
            if n % 2:
                for i in range(n - 1):
                    j = n - i - 1
                    for left in dfs(i):
                        for right in dfs(j):
                            res.append(TreeNode(0, left, right))
            return res

        return dfs(n)

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def allPossibleFBT(self, N):
        """
        :type N: int
        :rtype: List[TreeNode]
        """
        N -= 1
        if N == 0: return [TreeNode(0)]
        res = []
        for l in range(1, N, 2):
            for left in self.allPossibleFBT(l):
                for right in self.allPossibleFBT(N - l):
                    node = TreeNode(0)
                    node.left = left
                    node.right = right
                    res.append(node)
        return res

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func allPossibleFBT(n int) []*TreeNode {
	f := map[int][]*TreeNode{}
	var dfs func(n int) []*TreeNode
	dfs = func(n int) []*TreeNode {
		if v, ok := f[n]; ok {
			return v
		}
		if n == 1 {
			return []*TreeNode{&TreeNode{Val: 0} }
		}
		res := []*TreeNode{}
		for i := 0; i < n-1; i++ {
			j := n - i - 1
			for _, left := range dfs(i) {
				for _, right := range dfs(j) {
					res = append(res, &TreeNode{0, left, right})
				}
			}
		}
		f[n] = res
		return res
	}
	return dfs(n)
}

894 - All Possible Full Binary Trees

894. All Possible Full Binary Trees (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

894. All Possible Full Binary Trees (Medium)

Solution 1.

All Problems

All Solutions