本系列文章已全部上傳至我的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 程序員人生 版權所有
