将无序序列构造为二叉树
时间: 2023-07-16 16:15:36 浏览: 48
构造二叉树的过程可以分为两个步骤:
1. 将无序序列转化为有序序列
2. 以有序序列为基础构建二叉树
下面是具体的实现方法:
1. 将无序序列转化为有序序列
可以使用排序算法将无序序列转化为有序序列。例如,可以使用快速排序或归并排序来实现。这里以快速排序为例:
```
void quickSort(int arr[], int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
int partition(int arr[], int left, int right) {
int pivot = arr[left];
int i = left + 1;
int j = right;
while (i <= j) {
if (arr[i] < pivot) {
i++;
} else if (arr[j] > pivot) {
j--;
} else {
swap(arr[i], arr[j]);
i++;
j--;
}
}
swap(arr[left], arr[j]);
return j;
}
```
2. 以有序序列为基础构建二叉树
可以使用递归的方式,每次将有序序列的中间元素作为根节点,左边的元素构建左子树,右边的元素构建右子树。以此类推,直到所有元素都构建完毕。下面是具体的实现方法:
```
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int val): val(val), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector<int> nums, int left, int right) {
if (left > right) {
return NULL;
}
int mid = (left + right) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = buildTree(nums, left, mid - 1);
root->right = buildTree(nums, mid + 1, right);
return root;
}
TreeNode* buildTree(vector<int> nums) {
if (nums.empty()) {
return NULL;
}
return buildTree(nums, 0, nums.size() - 1);
}
```
这样就可以将无序序列构建成一棵二叉树了。