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
本題給定一棵二叉樹的前序排列和中序排列，要求構(gòu)造出這棵二叉樹。
前序排列的順序是：根節(jié)點(diǎn)——左節(jié)點(diǎn)——右節(jié)點(diǎn)
中序排列的順序是：左節(jié)點(diǎn)——根節(jié)點(diǎn)——右節(jié)點(diǎn)
因此設(shè)4個(gè)int型值，分別記錄當(dāng)前子樹的所有節(jié)點(diǎn)在前序、中序數(shù)列中位置。
若前序數(shù)列中某個(gè)值在中序數(shù)列中找到，則在中序數(shù)列中，前面的值是該節(jié)點(diǎn)左子樹的所有值（設(shè)有m個(gè)），后面的值是該節(jié)點(diǎn)右子樹的所有值（設(shè)有n個(gè)）。那么，在前序數(shù)列中，該值的后m個(gè)是它的左子樹所有值，m到m+n個(gè)是它的右子樹的所有值。
class Solution {
public:
? ? TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
? ? ? ? return work(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
? ? }
? ? TreeNode* work(vector<int>& preorder, vector<int>&inorder, int preleft, int preright, int inleft, int inright){
? ? ? ? if(preleft>preright) return NULL;
? ? ? ? TreeNode *root = new TreeNode(preorder[preleft]);
? ? ? ? for(int k=inleft; k<=inright; k++){
? ? ? ? ? ? if(inorder[k]==preorder[preleft]){
? ? ? ? ? ? ? ? root->left = work(preorder, inorder, preleft+1, preleft+k-inleft, inleft, k-1);
? ? ? ? ? ? ? ? root->right = work(preorder, inorder, preleft+k-inleft+1, preright, k+1, inright);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return root;
? ? }
};
