105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]

Return the following binary tree:

3 / \ 9 20 / \ 15 7

Solution

C++

/** * Definition for a binary tree node. * 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) { int rootindex = 0; return reverse(preorder, inorder, rootindex, 0, preorder.size()-1); } TreeNode* reverse(vector<int>& preorder, vector<int>& inorder, int& rootindex, int start, int end) { if(rootindex >= preorder.size() || start > end) return NULL; TreeNode* root = new TreeNode(preorder[rootindex]); int index; for(index = start; index <= end; index++) { if(inorder[index] == root->val) break; } ++rootindex; root->left = reverse(preorder, inorder, rootindex, start, index-1); root->right = reverse(preorder, inorder, rootindex, index+1, end); return root; } };

Explanation