Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
Subscribe to see which companies asked this question
伪代码：
buildTree(pbeg, ibeg, iend) front = preorder[pbeg] root = new Node(front) find front idx from inorder[ibeg to iend] root->left = buildTree(pbeg+1, ibeg, idx) root->right = buildTree(pbeg+1+index-ibeg, idx+1, iend) return root
递归方法实现：
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, size_t preBegin, size_t inBegin, size_t inEnd) { if (inBegin == inEnd) return nullptr; int front = preorder[preBegin]; TreeNode* root = new TreeNode(front); int index = inBegin; while (index < inEnd && inorder[index] != front) index++; root->left = buildTree(preorder, inorder, preBegin + 1, inBegin, index); root->right = buildTree(preorder, inorder, preBegin + 1 + index - inBegin, index+1, inEnd); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return buildTree(preorder, inorder, 0, 0, inorder.size()); }
Construct Binary Tree from Preorder and Inorder Traversal leetcode
原文：http://www.cnblogs.com/sdlwlxf/p/5173659.html