108.将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。示例 1：输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：输入：nums = [1,3] 输出：[3,1] 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
分析:
1.BST的中序遍历正好是有序序列, 给定中序遍历, 能否唯一确定一个二叉搜索树? 不能, 在没限制平衡的设定下, 任何一个数字都可以作为二叉搜索树的根节点
2.如果我们要求二叉搜索树平衡, 是否可以确定唯一一个二叉搜索树? 也不能. 举个反例是一个节点下面各两个子树, 但是每个子树下面2个唯一分支节点, 左孩子或者右孩子各种换位置都可以满足需求
3.那怎么能能确定根节点, 然后保证构造出来的一定是平衡的呢? 如果数组长度是奇数, 那么中间的节点是唯一可行的根节点, 如果偶数, 那么中间位置左边或者右边都能做根节点
4.中间位置是 int mid = l + (r - l) / 2
class Solution {
public:
TreeNode* construct(vector<int>& nums, int l, int r) {
if (l > r) {
return nullptr;
}
int mid = l + (r - l) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = construct(nums, l, mid - 1);
root->right = construct(nums, mid + 1, r);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return construct(nums, 0, nums.size()-1);
}
};
95.不同的二叉搜索树 II
给你一个整数 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.二叉搜索树的特点是, 左边的子树的节点都小于右子树, 同时所有的子树也是二叉搜索树
2.当我们对根节点 i, 假设可以生成它的所有的左子树 generate(low, i-1), 然后生成它的所有右子树 generate(i+1, high); 那么需要穷举所有左右子树的排列, 构成所有的可能, 此时我们得到了所有的以 i 为根节点的二叉搜索树
3.枚举所有的可能性, 设计函数 generate(low, high), 递归地实现枚举的过程
4.生成根节点i的一种二叉搜索树的时候, new 根节点, 然后左右孩子分别接入已经生成好的某一种左右子树结果
class Solution {
public:
vector<TreeNode*> generate(int low, int high) {
if (low > high) {
return {nullptr};
}
vector<TreeNode*> trees;
for (int i = low; i <= high; ++i) {
vector<TreeNode*> left = generate(low, i-1);
vector<TreeNode*> right = generate(i + 1, high);
for (auto& l : left) {
for (auto& r : right) {
TreeNode* root = new TreeNode(i);
root->left = l;
root->right = r;
trees.emplace_back(root);
}
}
}
return trees;
}
vector<TreeNode*> generateTrees(int n) {
return generate(1, n);
}
};
96.不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：输入：n = 3 输出：5
示例 2：输入：n = 1 输出：1
1.采用构建所有二叉搜索树的方法, 但是会报超时
class Solution {
public:
vector<TreeNode*> generate(int low, int high) {
if (low > high) {
return {nullptr};
}
vector<TreeNode*> trees;
for (int i = low; i <= high; ++i) {
vector<TreeNode*> left = generate(low, i-1);
vector<TreeNode*> right = generate(i + 1, high);
for (auto& l : left) {
for (auto& r : right) {
TreeNode* root = new TreeNode(i);
root->left = l;
root->right = r;
trees.emplace_back(root);
}
}
}
return trees;
}
int numTrees(int n) {
vector<TreeNode*> res = generate(1, n);
return res.size();
}
};
转载请注明来源, from goldandrabbit.github.io
