What is a full binary tree?

A full binary tree is a binary tree where each node has either 0 or 2 children, with no nodes having only one child.

How can I optimize my solution for All Possible Full Binary Trees?

You can optimize the solution using dynamic programming and memoization, which reduces redundant calculations by storing previously computed subtrees.

What is the key idea behind solving this problem?

The key idea is recursively constructing valid subtrees and combining them efficiently, leveraging memoization to optimize repeated calculations.

How do I handle large inputs for this problem?

To handle larger values of `n`, it's crucial to implement an optimized approach using dynamic programming with memoization, which reduces the time complexity significantly.

What pattern does this problem involve?

This problem is a classic example of binary tree traversal and state tracking, where dynamic programming and recursion are essential for an efficient solution.

#894

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

所有可能的真二叉树

给你一个整数 n ，请你找出所有可能含 n 个节点的真二叉树，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。答案的每个元素都是一棵真二叉树的根节点。你可以按任意顺序返回最终的真二叉树列表。真二叉树是一类二叉树，树中每个节点恰好有 0 或 2 个子节…

动态规划树递归记忆化二叉树

题目描述

给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。

答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。

真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。

示例 1：

输入：n = 7
输出：[[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]]

示例 2：

输入：n = 3
输出：[[0,0,0]]

提示：

1 <= n <= 20

lightbulb

解题思路

方法一：记忆化搜索

如果 $n=1$ ，直接返回单个节点的列表。

如果 $n \gt 1$ ，我们可以枚举左子树的节点数量 $i$ ，那么右子树的节点数量为 $n-1-i$ 。对于每种情况，我们递归地构造左子树和右子树的所有可能的真二叉树。然后将左子树和右子树两两组合，得到所有可能的真二叉树。

此过程可以用记忆化搜索，避免重复计算。

时间复杂度 $O(\frac{2^n}{\sqrt{n}})$ ，空间复杂度 $O(\frac{2^n}{\sqrt{n}})$ 。其中 $n$ 是节点数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# 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: int) -> List[Optional[TreeNode]]:
            if n == 1:
                return [TreeNode()]
            ans = []
            for i in range(n - 1):
                j = n - 1 - i
                for left in dfs(i):
                    for right in dfs(j):
                        ans.append(TreeNode(0, left, right))
            return ans

        return dfs(n)

speed

复杂度分析

指标	值
时间	O(2^{n/2})
空间	O(n \cdot 2^{n/2})

psychology

面试官常问的追问

外企场景

question_mark
Understand recursion and dynamic programming to optimize tree construction.
question_mark
Recognize overlapping subproblems and apply memoization effectively.
question_mark
Be able to explain how combining subtrees leads to generating full binary trees.

warning

常见陷阱

外企场景

error
Forgetting to memoize the results of subproblems, leading to unnecessary recalculations.
error
Incorrectly handling the base case or subtree splitting, resulting in invalid trees.
error
Overlooking the efficiency trade-off, which could result in performance issues for larger values of `n`.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to return all possible unique full binary trees of height `h` instead of a fixed number of nodes.
arrow_right_alt
Alter the problem by adding constraints on the values of the nodes (not just 0).
arrow_right_alt
Change the tree structure to allow a binary tree with nodes having 1, 2, or more children.

help

常见问题

外企场景

继续练习

#1569 将子数组重新排序得到同一个二叉搜索树的方案数 #968 监控二叉树 #1372 二叉树中的最长交错路径