LeetCode 654: 最大二叉树 - 详细剖析与多种解法
LeetCode 654: 最大二叉树 - 详细剖析与多种解法在LeetCode上，第654题要求我们构建一个“最大二叉树”。题目描述如下：给定一个不含重复元素的整数数组 nums，构建一个最大二叉树。最大二叉树的定义是：
[*]根节点是数组中的最大值。
[*]左子树是通过数组中最大值左侧的子数组构建的最大二叉树。
[*]右子树是通过数组中最大值右侧的子数组构建的最大二叉树。
本文将详细剖析两种不同的解法，帮助你更好地理解如何构建最大二叉树。
解法一：递归 + 区间分别
代码实现
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return buildTree(nums, 0, nums.size() - 1);
}
TreeNode* buildTree(vector<int>& nums, int left, int right) {
if (left > right) return nullptr; // 递归终止条件
// 找到当前区间 的最大值及其索引
int maxIndex = left;
for (int i = left + 1; i <= right; ++i) {
if (nums > nums) {
maxIndex = i;
}
}
// 创建根节点
TreeNode* root = new TreeNode(nums);
// 递归构建左子树和右子树
root->left = buildTree(nums, left, maxIndex - 1);
root->right = buildTree(nums, maxIndex + 1, right);
return root;
}
};
剖析
[*]递归终止条件：当 left > right 时，表现当前区间为空，返回 nullptr。
[*]探求最大值及其索引：在当前区间 内，遍历数组找到最大值及其索引 maxIndex。
[*]构建根节点：使用最大值 nums 创建一个新的 TreeNode 作为根节点。
[*]递归构建左子树和右子树：分别对最大值左侧和右侧的子数组举行递归调用，构建左子树和右子树。
时间复杂度
• 每次递归都必要遍历当前区间以找到最大值，因此时间复杂度为 O(n^2)，其中 n 是数组的长度。
空间复杂度
• 递归栈的深度最坏情况下为 O(n)，因此空间复杂度为 O(n)。
解法二：递归 + 数组分割
代码实现
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
TreeNode* node = new TreeNode(0);
if (nums.size() == 1) {
node->val = nums;
return node;
}
// 找到数组中最大的值和对应的下标
int maxValue = 0;
int maxValueIndex = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums > maxValue) {
maxValue = nums;
maxValueIndex = i;
}
}
node->val = maxValue;
// 最大值所在的下标左区间 构造左子树
if (maxValueIndex > 0) {
vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
node->left = constructMaximumBinaryTree(newVec);
}
// 最大值所在的下标右区间 构造右子树
if (maxValueIndex < (nums.size() - 1)) {
vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
node->right = constructMaximumBinaryTree(newVec);
}
return node;
}
};
剖析
[*]递归终止条件：当数组长度为1时，直接返回该值作为叶子节点。
[*]探求最大值及其索引：遍历数组找到最大值 maxValue 及其索引 maxValueIndex。
[*]构建根节点：使用最大值 maxValue 创建一个新的 TreeNode 作为根节点。
[*]数组分割：将数组分为左子数组和右子数组，分别对这两个子数组举行递归调用，构建左子树和右子树。
时间复杂度
• 每次递归都必要遍历整个数组以找到最大值，因此时间复杂度为 O(n^2)，其中 n 是数组的长度。
空间复杂度
• 递归栈的深度最坏情况下为 O(n)，同时每次递归都会创建新的子数组，因此空间复杂度为 O(n^2)。
总结
两种解法都接纳了递归的思想，但在详细实现上有所不同：
• 解法一通过传递区间的左右边界来避免创建新的子数组，节省了空间。
• 解法二则直接通过分割数组来构建子树，代码更加直观，但空间开销较大。
两种解法的时间复杂度相同，但解法一在空间复杂度上更优。根据实际需求，可以选择不同的实现方式。
欢迎各人在批评区留言讨论，如果有任何题目或建议，也欢迎提出！
关注我，获取更多数据布局与算法的干货内容！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]