根据前序和中序遍历构造二叉树,保证val不重复。注意别超内存。
class Solution { public: TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { // Note: The Solution object is instantiated only once and is reused by each test case. if(preorder.size() <= 0 || inorder.size() <= 0) return NULL; TreeNode * root = buildTreeStep(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1); return root; } private: TreeNode *buildTreeStep(vector<int> &preorder,int prea,int preb, vector<int> &inorder,int ina,int inb) { if(prea > preb || ina > inb) return NULL; int root = preorder[prea]; int i; for(i = ina;i <= inb;i++) { if(inorder[i] == root) { break; } } //inorderleft:ina,i-1 //inorderright,i+1,inb //preorderleft:prea+1,prea+1+(i-1)-ina //preorderright:prea+(i-1)-ina+1,preb TreeNode * node = new TreeNode(root); node->left = buildTreeStep(preorder,prea+1,prea+1+(i-1)-ina,inorder,ina,i-1); node->right = buildTreeStep(preorder,prea+1+(i-1)-ina+1,preb,inorder,i+1,inb); return node; } };