C++根据二叉树的先序序列和中序序列确定二叉树,并画出二叉树的形状,用/和\表示左右子树代码
时间: 2024-05-25 12:09:04 浏览: 13
确定一棵二叉树的过程如下:
1. 先序序列的第一个元素为根节点。
2. 在中序序列中找到根节点,根节点左边的为左子树的中序序列,右边的为右子树的中序序列。
3. 在先序序列中,根节点后面紧跟着的若干个元素为左子树的先序序列,剩余的为右子树的先序序列。
根据以上规则,可以递归构建整棵二叉树。
以下是C++代码实现:
```
#include <iostream>
#include <unordered_map>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
for (int i = 0; i < n; i++) {
map[inorder[i]] = i;
}
return build(preorder, inorder, 0, n - 1, 0, n - 1);
}
private:
unordered_map<int, int> map;
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preLeft, int preRight, int inLeft, int inRight) {
if (preLeft > preRight) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[preLeft]);
int inRoot = map[root->val];
int numsLeft = inRoot - inLeft;
root->left = build(preorder, inorder, preLeft + 1, preLeft + numsLeft, inLeft, inRoot - 1);
root->right = build(preorder, inorder, preLeft + numsLeft + 1, preRight, inRoot + 1, inRight);
return root;
}
};
void print(TreeNode* root, int space)
{
if (root == NULL)
return;
space += 5;
print(root->right, space);
cout << endl;
for (int i = 5; i < space; i++)
cout << " ";
cout << root->val << "\n";
print(root->left, space);
}
int main()
{
vector<int> preorder{ 1,2,4,5,3,6 };
vector<int> inorder{ 4,2,5,1,6,3 };
Solution s;
TreeNode* root = s.buildTree(preorder, inorder);
print(root, 0);
return 0;
}
```
输出结果如下:
```
3
6
1
5
2
4
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)