题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
样例
算法1
C++ 代码
class Solution {
TreeNode* CreatTree(vector<int>& preorder, vector<int>& inorder,int l1, int r1,int l2, int r2 )
{
if(l1>r1 || l2>r2) return NULL;
TreeNode* root = new TreeNode(preorder[l1]);
int rootin = l2;
while(rootin <= r2 && inorder[rootin]!=preorder[l1]) rootin++;
//计算左子树数量
int left = rootin -l2;
//左子树在前序遍历的边界【l1+1,l1+left】
root->left = CreatTree(preorder,inorder,l1+1,l1+left,l2,rootin-1);
//右子树在前序遍历的边界【l1+left+1,r1】
root->right = CreatTree(preorder,inorder,l1+left+1,r1,rootin+1,r2);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return CreatTree(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
}
};