本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github
欢迎大家关注我的新浪微博，我的新浪微博
欢迎转载，转载请注明出处
来源：https://leetcode.com/problems/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.
题目大意：根据2叉树的前序和中序遍历，构造出该2叉树
剑指offer上的老题了，前序遍历的第1个节点为根节点，在中序遍历中找到该节点，其左侧为根节点的左子树，后边为根节点的右子树。顺次递归下去便可以重构出该2叉树。
如：123和213，前序遍历找出根节点为1，在中序遍历213中找出1，则2为左子树，3为右子树。
/**
* 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:
typedef vector<int>::iterator vi;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.empty()||inorder.empty()) return (TreeNode*)NULL;
vi preStart = preorder.begin();
vi preEnd = preorder.end()-1;
vi inStart = inorder.begin();
vi inEnd = inorder.end()-1;
return constructTree(preStart,preEnd,inStart,inEnd);
}
TreeNode* constructTree(vi preStart,vi preEnd,vi inStart,vi inEnd)
{
//表示该节点为NULL
if(preStart>preEnd||inStart>inEnd) return NULL;
//前序遍历的第1个节点为根节点
TreeNode* root = new TreeNode(*preStart);
//只有1个节点的时候直接返回
if(preStart==preEnd||inStart==inEnd) return root;
vi rootIn = inStart;
while(rootIn!=inEnd){//在中序遍历中找出根节点
if(*rootIn==*preStart) break;
else ++rootIn;
}
root->left = constructTree(preStart+1,preStart+(rootIn-inStart),inStart,rootIn-1);//递归构造左子树
root->right = constructTree(preStart+(rootIn-inStart)+1,preEnd,rootIn+1,inEnd);//递归构造右子树
return root;
}
};
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
