C++先根和中根遍历构造二叉树
时间: 2023-12-18 21:03:42 浏览: 32
假设我们已经有了二叉树的节点定义:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
那么,我们可以通过先序遍历和中序遍历构造出一棵二叉树。具体思路如下:
1. 在先序遍历中,第一个节点一定是根节点。我们可以找到根节点在中序遍历中的位置,然后将中序遍历分成左子树和右子树两部分。
2. 在先序遍历中,根节点的下一个节点一定是左子树的根节点。同样,我们可以找到左子树的根节点在先序遍历中的位置,然后将先序遍历分成左子树和右子树两部分。
3. 在中序遍历中,左子树的节点都在根节点的左侧,右子树的节点都在根节点的右侧。同样,我们也可以将中序遍历分成左子树和右子树两部分。
4. 递归地构造左子树和右子树。
下面是基于上述思路的C++代码实现:
```c++
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return nullptr;
}
int rootVal = preorder[preStart];
int rootIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
TreeNode* root = new TreeNode(rootVal);
root->left = buildTreeHelper(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1);
root->right = buildTreeHelper(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd);
return root;
}
};
```
其中,`buildTreeHelper`函数用于递归地构造子树。`buildTree`函数是入口函数,用于调用`buildTreeHelper`函数,并返回整棵二叉树的根节点。