上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 4.2 MB, 提交时间: 2022-11-17 22:33:48
func generateTrees(n int) []*TreeNode {
if n == 0 {
return nil
}
return helper(1, n)
}
func helper(start, end int) []*TreeNode {
if start > end {
return []*TreeNode{nil}
}
allTrees := []*TreeNode{}
// 枚举可行根节点
for i := start; i <= end; i++ {
// 获得所有可行的左子树集合
leftTrees := helper(start, i - 1)
// 获得所有可行的右子树集合
rightTrees := helper(i + 1, end)
// 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
for _, left := range leftTrees {
for _, right := range rightTrees {
currTree := &TreeNode{i, nil, nil}
currTree.Left = left
currTree.Right = right
allTrees = append(allTrees, currTree)
}
}
}
return allTrees
}
python3 解法, 执行用时: 60 ms, 内存消耗: 16.8 MB, 提交时间: 2022-11-17 22:32:20
# 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
'''
回溯法
二叉搜索树关键的性质是根节点的值大于左子树所有节点的值，小于右子树所有节点的值，且左子树和右子树也同样为二叉搜索树。
因此在生成所有可行的二叉搜索树的时候，假设当前序列长度为 n，如果我们枚举根节点的值为 i，
那么根据二叉搜索树的性质我们可以知道左子树的节点值的集合为 [1…i−1]，右子树的节点值的集合为 [i+1…n]。
而左子树和右子树的生成相较于原问题是一个序列长度缩小的子问题，因此我们可以想到用回溯的方法来解决这道题目。
我们定义 generateTrees(start, end) 函数表示当前值的集合为 [start, end]，返回序列 [start, end] 生成的所有可行的二叉搜索树。
'''
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
def generateTrees(start, end):
if start > end:
return [None,]
allTrees = []
for i in range(start, end + 1): # 枚举可行根节点
# 获得所有可行的左子树集合
leftTrees = generateTrees(start, i - 1)
# 获得所有可行的右子树集合
rightTrees = generateTrees(i + 1, end)
# 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
for l in leftTrees:
for r in rightTrees:
currTree = TreeNode(i)
currTree.left = l
currTree.right = r
allTrees.append(currTree)
return allTrees
return generateTrees(1, n) if n else []
