根据层序遍历构造二叉树c++
时间: 2023-08-06 22:07:54 浏览: 36
可以使用队列来实现层序遍历构造二叉树的方法:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* constructTree(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 (i < nums.size() && nums[i] != -1) {
cur->left = new TreeNode(nums[i]);
q.push(cur->left);
}
i++;
if (i < nums.size() && nums[i] != -1) {
cur->right = new TreeNode(nums[i]);
q.push(cur->right);
}
i++;
}
return root;
}
```
其中,-1代表空节点,nums是层序遍历的结果,从左到右、从上到下按顺序存储。实现方法是,先将第一个节点作为根节点,然后将根节点入队,从第二个节点开始,每次取出队首元素,如果当前节点的左孩子不为空,则将其加入队列,如果当前节点的右孩子不为空,则将其加入队列。最后返回根节点即可。