C语言实现最大二叉树构建算法及时间空间复杂度分析

C语言实现最大二叉树构建算法及时间空间复杂度分析

给定一个非空且无重复元素的整数数组 A，它对应的'最大二叉树' T(A) 定义为：

1. T(A) 的根为 A 中最大值元素；2. T(A) 左子树为 A 中最大值左侧部分对应的'最大二叉树'；3. T(A) 右子树为 A 中最大值右侧部分对应的'最大二叉树'。

算法思路

1. 找出数组 A 中的最大值，以此作为根节点；2. 将 A 数组分为左右两个子数组，左子数组包含最大值左侧的元素，右子数组包含最大值右侧的元素；3. 对左子数组和右子数组分别递归构建最大二叉树，并作为根节点的左右子树。

代码实现c#include <stdlib.h>#include <stdio.h>

typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right;} TreeNode;

TreeNode* constructMaximumBinaryTree(int* nums, int left, int right) { if (left > right) { return NULL; } int maxIndex = left; for (int i = left + 1; i <= right; i++) { if (nums[i] > nums[maxIndex]) { maxIndex = i; } } TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->val = nums[maxIndex]; root->left = constructMaximumBinaryTree(nums, left, maxIndex - 1); root->right = constructMaximumBinaryTree(nums, maxIndex + 1, right); return root;}

int main() { int nums[] = {3, 2, 1, 6, 0, 5}; TreeNode* root = constructMaximumBinaryTree(nums, 0, 5); printf('Root: %d ', root->val); printf('Left child: %d ', root->left->val); printf('Right child: %d ', root->right->val); return 0;}

时间复杂度

• 最好情况: 数组 A 中的元素均匀分布，每个元素都会被遍历一次，因此时间复杂度为 O(n)。- 最坏情况: 数组 A 中的元素呈现单调递增或递减，每次递归时只能减少一个元素，因此时间复杂度为 O(n^2)。

空间复杂度

• 最好情况: 数组 A 中的元素均匀分布，递归深度为 O(log n)，因此空间复杂度为 O(log n)。- 最坏情况: 数组 A 中的元素呈现单调递增或递减，递归深度为 O(n)，因此空间复杂度为 O(n)