1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| class Solution { private: TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) { if (preorderBegin == preorderEnd) return nullptr;
int rootValue = preorder[preorderBegin]; TreeNode* root = new TreeNode(rootValue); if (preorderEnd - preorderBegin == 1) return root;
int delimiterIndex = inorderBegin; for (; delimiterIndex < inorderEnd; delimiterIndex++) { if (inorder[delimiterIndex] == rootValue) break; } int leftInorderBegin = inorderBegin; int leftInorderEnd = delimiterIndex; int rightInorderBegin = delimiterIndex + 1; int rightInorderEnd = inorderEnd;
int leftPreorderBegin = preorderBegin + 1; int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; int rightPreorderBegin = preorderBegin + 1 + delimiterIndex - inorderBegin; int rightPreorderEnd = preorderEnd;
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, preorder, leftPreorderBegin, leftPreorderEnd); root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);
return root; }
public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size()); } };
|