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: Recursion
Preprocessing: use a hashtable to store the index of element in preorder array.
For an element in inorder array, find the pos of it in preorder array in O(1), anything to the left will be the leftchild and anything to the right will be the right child.
e.g.
buildTree([9, 3, 15, 20, 7], [3, 9, 20, 15, 7]):
root = TreeNode(9) # inorder[0] = 9
root.left = buildTree([3], [3])
root.right = buildTree([15, 20, 7], [20, 15, 7])
return root
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua class Solution { public: TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { unordered_map<int, int> pos; for (int i = 0; i < inorder.size(); i++) pos[inorder[i]] = i; function<TreeNode*(int, int, int, int)> buildTree = [&](int is, int ie, int ps, int pe) { if (ps > pe) return (TreeNode*)nullptr; int im = pos[preorder[ps]]; int pm = ps + (im - is); auto root = new TreeNode(preorder[ps]); root->left = buildTree(is, im - 1, ps + 1, pm); root->right = buildTree(im + 1, ie, pm + 1, pe); return root; }; return buildTree(0, inorder.size() - 1, 0, preorder.size() - 1); } }; |
Related Problems
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment