根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/
9 20
/
15 7
思路：前序遍历先访问根节点，因此前序遍历序列的第一个字母肯定就是根节点；然后，由于中序遍历先访问左子树，再访问根节点，最后访问右子树，所以我们找到中序遍历中根节点的位置，然后它左边的字母就是左子树了；同样的，它右边的就是右子树。
将前序遍历序列也按照中序遍历的分隔分成两部分，分别对左子树和右子树应用同样的方法，递归下去，二叉树就成功构建好了。
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int size = preorder.size(); if(size==0 || inorder.empty()) { return NULL; } int r = preorder[0];//在前序遍历中。第一个节点就是我们所求二叉树的根节点 TreeNode* root = new TreeNode(r); int p=0; for(;p<size;p++) { if(inorder[p]==r)//在中序遍历中找到根节点的位置 break; } vector<int> pre_left,pre_right,in_left,in_right; for(int i=0;i<size;i++) { if(i<p) { pre_left.push_back(preorder[i+1]);//前序遍历中，从头到中序遍历的根节点的位置p，这个区间上的点是左子树的前序遍历 in_left.push_back(inorder[i]);//中序遍历中，从头到根节点的位置p，这个区间的点是左子树的中序遍历 } else if(i>p) { pre_right.push_back(preorder[i]);//前序遍历中，从位置p到末尾，这个区间是右子树的前序遍历 in_right.push_back(inorder[i]);//中序遍历中，从位置p到末尾，这个区间是右子树的中序遍历 } } root->left = buildTree(pre_left,in_left);//递归实现左子树和右子树的重建过程 root->right = buildTree(pre_right,in_right); return root; }
当然还有非递归的方法，也是利用栈来完成的，但是思路不是很好理解。谨附下代码
TreeNode* buildTree(vector<char>& preorder, vector<char>& inorder) { if(preorder.empty()) return NULL; TreeNode* t=new TreeNode(preorder[0]),*p=t; stack<TreeNode*> roots; int size=preorder.size(), i=0,j=0; while(j<size-1) { // roots.push(p); while(preorder[i++]!=inorder[j]) { p->left=new TreeNode(preorder[i]); roots.push(p); p=p->left; } if(i==size) break; while(++j<size&&!roots.empty()&&inorder[j]==roots.top()->val) { p=roots.top(); roots.pop(); } p->right=new TreeNode(preorder[i]); p=p->right; } return t; }