根据先序序列、中序序列建立二叉树,给出cpp代码示例
时间: 2023-12-21 17:03:33 浏览: 81
以下是根据先序序列和中序序列构建二叉树的C++代码示例:
```cpp
#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) {
unordered_map<int, int> map;
for(int i=0; i<inorder.size(); i++) {
map[inorder[i]] = i;
}
return buildTreeHelper(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1, map);
}
TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd, unordered_map<int, int>& map) {
if(preStart > preEnd || inStart > inEnd) {
return NULL;
}
int rootVal = preorder[preStart];
TreeNode* root = new TreeNode(rootVal);
int rootIndex = map[rootVal];
int leftSubtreeSize = rootIndex - inStart;
root->left = buildTreeHelper(preorder, preStart+1, preStart+leftSubtreeSize, inorder, inStart, rootIndex-1, map);
root->right = buildTreeHelper(preorder, preStart+leftSubtreeSize+1, preEnd, inorder, rootIndex+1, inEnd, map);
return root;
}
};
```
其中,`buildTree`函数接收先序序列和中序序列,返回构建完成的二叉树。`buildTreeHelper`函数是递归函数,用于构建二叉树的子树。通过使用哈希表记录中序序列中每个元素的下标,可以快速查找根节点在中序序列中的位置,从而方便地划分左右子树。
阅读全文