输入一个带有null和数字的数组,把它生成一棵树,C++
时间: 2023-12-01 09:02:43 浏览: 30
好的,以下是一个简单的C++程序,用于将输入的数组转换成二叉树:
```c++
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector<int>& nums) {
if (nums.empty()) return NULL;
queue<TreeNode*> q;
TreeNode* root = new TreeNode(nums[0]);
q.push(root);
int i = 1;
while (!q.empty() && i < nums.size()) {
TreeNode* cur = q.front();
q.pop();
if (nums[i] != NULL) {
cur->left = new TreeNode(nums[i]);
q.push(cur->left);
}
i++;
if (i < nums.size() && nums[i] != NULL) {
cur->right = new TreeNode(nums[i]);
q.push(cur->right);
}
i++;
}
return root;
}
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
int main() {
vector<int> nums = { 1,2,3,NULL,5,6,7 };
TreeNode* root = buildTree(nums);
inorderTraversal(root);
return 0;
}
```
输入的数组中,NULL表示该位置上没有节点,否则在该位置上创建一个值为该数字的节点。使用队列进行层次遍历,依次处理每一层的节点。时间复杂度为O(n),空间复杂度为O(n)。