给你一个整数 n ,请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
示例 1:
输入:n = 3 输出:[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2:
输入:n = 1 输出:[[1]]
提示:
1 <= n <= 8 解题思路:
枚举所有可行的根节点,生成所有可行的左子树和右子树的集合。
从左子树和右子树上各取一个子树拼接到根节点上。
class Solution { public: vectorgetGenerateTree(int start, int end) { if (start > end) return {nullptr}; vector allTree; for (int i = start; i <= end; i++) { vector leftTrees = getGenerateTree(start, i - 1); vector rightTrees = getGenerateTree(i + 1, end); for (auto left:leftTrees) { for (auto right:rightTrees) { TreeNode* curTree = new TreeNode(i); curTree->left = left; curTree->right = right; allTree.push_back(curTree); } } } return allTree; } vector generateTrees(int n) { if (!n) return {}; return getGenerateTree(1, n); } };
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)