二手车网站策划,wordpress更新方法,网页制作的常用工具,哈尔滨餐饮网站建设LeetCode-894. 所有可能的真二叉树【树 递归 记忆化搜索 动态规划 二叉树】 题目描述#xff1a;解题思路一#xff1a;分治#xff0c;递归解题思路二#xff1a;动态规划。关键思路是如果构造节点数目为 n 的真二叉树#xff0c;此时可以从节点数目序列为 [(1,n−2),(3,… LeetCode-894. 所有可能的真二叉树【树 递归 记忆化搜索 动态规划 二叉树】 题目描述解题思路一分治递归解题思路二动态规划。关键思路是如果构造节点数目为 n 的真二叉树此时可以从节点数目序列为 [(1,n−2),(3,n−5),⋯ ,(n−2,1)]的真二叉树中构成按照所有可能的组合数进行枚举即可构造成节点数目为 n 的真二叉树。即左子树分配1,3,5, ... , n-2个节点。解题思路三0 题目描述
给你一个整数 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
解题思路一分治递归
如果你要为某节点分配一个左节点那么一定也要为它分配一个右节点。因此如果 N 为偶数那一定无法构成一棵满二叉树。
为了列出所有满二叉树的排列我们可以为左子树分配 x 节点为右子树分配 N - 1 - x其中减 1 减去的是根节点节点然后递归地构造左右子树。
x 的数目从 1 开始每次循环递增数目 2多增加 2 个节点等于多增加 1 层。
递归过程 递归最关心的两个问题是
结束条件自身调用
对于这个问题来说结束条件为
当 N 为偶数时无法构造满二叉树返回空数组当 N 1 时树只有一个节点直接返回包含这个节点的数组当完成 N 个节点满二叉树构造时返回结果数组 当需要构造左右子树时就进行自身调用。具体的看代码吧~
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def allPossibleFBT(self, n: int) - List[Optional[TreeNode]]:res []if n 1:return [TreeNode(0)]if n % 2 0: # 结点个数必须是奇数return []left_num 1 # 左子树分配一个节点right_num n - 2 # 此时n必大于等于3 右子树可以分配到 n - 1 - 1 n - 2 个节点while right_num 0:left_tree self.allPossibleFBT(left_num) # 递归构造左子树right_tree self.allPossibleFBT(right_num) # 递归构造右子树# 具体构造过程for i in range(len(left_tree)):for j in range(len(right_tree)):root TreeNode(0)root.left left_tree[i]root.right right_tree[j]res.append(root) # 注意返回的是树的根节点left_num 2right_num - 2return res时间复杂度O(2n / n \sqrt n n ) 空间复杂度O(n) 递归调用栈
解题思路二动态规划。关键思路是如果构造节点数目为 n 的真二叉树此时可以从节点数目序列为 [(1,n−2),(3,n−5),⋯ ,(n−2,1)]的真二叉树中构成按照所有可能的组合数进行枚举即可构造成节点数目为 n 的真二叉树。即左子树分配1,3,5, … , n-2个节点。
动规五部曲定推初遍举
dp定义所有可能含 n 个节点的 真二叉树推导dp[n] 节点数目序列为 [(1,n−2),(3,n−5),⋯ ,(n−2,1)]的真二叉树中构成初始化dp[1] [TreeNode(0)]遍历按照推导公式来for i in range(3, n 1, 2): for j in range(1, i, 2):举例注意dp[i]是一个列表
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def allPossibleFBT(self, n: int) - List[Optional[TreeNode]]:if n % 2 0: # 结点个数必须是奇数return []dp [[] for _ in range(n1)]dp[1] [TreeNode(0)]for i in range(3, n 1, 2):for j in range(1, i, 2):for left_tree in dp[j]:for right_tree in dp[i - 1 - j]:root TreeNode(0, left_tree, right_tree)dp[i].append(root)return dp[n]时间复杂度O(2n / n \sqrt n n ) 空间复杂度O(1)返回值不计入空间复杂度。
解题思路三0 时间复杂度O(n) 空间复杂度O(n)
